Approximation Algorithms for Vertex Happiness

  • PDF / 389,997 Bytes
  • 20 Pages / 439.37 x 666.142 pts Page_size
  • 72 Downloads / 225 Views

DOWNLOAD

REPORT


Approximation Algorithms for Vertex Happiness Yao Xu1

· Yong Chen2 · Peng Zhang3 · Randy Goebel1

Received: 3 September 2018 / Revised: 10 April 2019 / Accepted: 1 July 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019

Abstract We investigate the maximum happy vertices (MHV) problem and its complement, the minimum unhappy vertices (MUHV) problem. In order to design better approximation algorithms, we introduce the supermodular and submodular multi-labeling (Sup- ML and Sub- ML) problems and show that MHV and MUHV are special cases of Sup- ML and Sub- ML, respectively, by rewriting the objective functions as set functions. The convex relaxation on the Lovász extension, originally presented for the submodular multi-partitioning problem, can be extended for the Sub- ML problem, thereby proving that Sub- ML (Sup- ML, respectively) can be approximated within a factor of 2 − 2/k (2/k, respectively), where k is the number of labels. These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2 − 2/k, respectively, using the same approximation algorithms. For the MUHV problem, we also show that it is approximation-equivalent to the hypergraph multiway cut problem; thus, MUHV is Unique Games-hard to achieve a (2 − 2/k − ε)-approximation, for

This paper is dedicated to Professor Ding-Zhu Du in celebration of his 70th birthday. This research was supported by the National Natural Science Foundation of China (Nos. 11771114, 11571252, and 61672323), the China Scholarship Council (No. 201508330054), the Natural Science Foundation of Shandong Province (No. ZR2016AM28), and the Natural Sciences and Engineering Research Council of Canada.

B

Yao Xu [email protected] Yong Chen [email protected] Peng Zhang [email protected] Randy Goebel [email protected]

1

Department of Computing Science, University of Alberta, Edmonton, AB T6G 2E8, Canada

2

Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, China

3

School of Computer Science and Technology, Shandong University, Jinan 250101, China

123

Y. Xu et al.

any ε > 0. For the MHV problem, the 2/k-approximation improves the previous best  approximation ratio max{1/k, 1/ Δ + 1/g(Δ) }, where Δ is the maximum vertex √ √ degree of the input graph and g(Δ) = ( Δ + Δ + 1)2 Δ > 4Δ2 . We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovász extension for Sup- ML; we then prove an upper bound of 2/k on the integrality gap of this LP relaxation, which suggests that the 2/k-approximation is the best possible based on this LP relaxation. Lastly, we prove that it is Unique Games-hard to approximate the MHV problem within a factor of Ω(log2 k/k). Keywords Vertex happiness · Multi-labeling · Submodular/supermodular set function · Approximation algorithm · Polynomial-time reduction · Integrality gap Mathematics Subject Classification 68W25 · 90C05 · 90C27

1 Introduction In

Data Loading...