Journal of the Operations Research Society of China >

2019 , Vol. 7 >Issue 3: 429 - 448

DOI: https://doi.org/10.1007/s40305-019-00260-1

Approximation Algorithms for Vertex Happiness

Expand
  • 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

Received date: 2018-09-03

  Revised date: 2019-04-10

  Online published: 2019-10-08

Fold

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-partitioningproblem,canbeextendedfortheSub-MLproblem,therebyproving 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 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).

Key words： Vertex happiness; Multi-labeling; Submodular/supermodular set function; Approximation algorithm; Polynomial-time reduction; Integrality gap

Cite this article

Yao Xu, Yong Chen, Peng Zhang, Randy Goebel . Approximation Algorithms for Vertex Happiness[J]. Journal of the Operations Research Society of China, 2019 , 7(3) : 429 -448 . DOI: 10.1007/s40305-019-00260-1

References

[1] Zhang, P., Li, A.:Algorithmic aspects of homophyly of networks. Theor. Comput. Sci. 593, 117-131(2015)
[2] Harary, F.:Graph Theory. Addison-Wesley, Reading (1969)
[3] Lovász, L.:Submodular functions and convexity. In:Bachem, A., Grötschel, M., Korte, B. (eds.) Mathematical Programming the State of the Art, pp. 235-257. Springer, Berlin (1983)
[4] Zhang, P., Jiang, T., Li, A.:Improved approximation algorithms for the maximum happy vertices and edgesproblems.In:Wang,L.,Zhu,D.(eds.)InternationalComputingandCombinatoricsConference, pp. 159-170. Springer, Berlin (2015)
[5] Zhang, P., Xu, Y., Jiang, T., Li, A., Lin, G., Miyano, E.:Improved approximation algorithms for the maximum happy vertices and edges problems. Algorithmica 80(5), 1412-1438(2017)
[6] Zhao,L.,Nagamochi,H.,Ibaraki,T.:Greedysplittingalgorithmsforapproximatingmultiwaypartition problems. Math. Prog. 102, 167-183(2005)
[7] Chekuri, C., Ene, A.:Approximation algorithms for submodular multiway partition. In:IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011, IEEE, pp. 807-816(2011a)
[8] Ene, A., Vondrák, J., Wu, Y.:Local distribution and the symmetry gap:Approximability of multiway partitioning problems. In:Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 306-325(2013)
[9] Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.:The complexity of multiterminal cuts. SIAM J. Comput. 23, 864-894(1994)
[10] Garg, N., Vazirani, V.V., Yannakakis, M.:Multiway cuts in node weighted graphs. J. Algorithms 50, 49-61(2004)
[11] Okumoto, K., Fukunaga, T., Nagamochi, H.:Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica 62, 787-806(2012)
[12] Čalinescu, G., Karloff, H., Rabani, Y.:An improved approximation algorithm for multiway cut. In:Proceedings of the thirtieth annual ACM symposium on Theory of computing, ACM, pp. 48-52(1998)
[13] Freund, A., Karloff, H.:A lower bound of 8/(7+ 1/k-1) on the integrality ratio of the Čalinescu-Karloff-Rabani relaxation for multiway cut. Inf. Process. Lett. 75, 43-50(2000)
[14] Karger, D.R., Klein, P., Stein, C., Thorup, M., Young, N.E.:Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29, 436-461(2004)
[15] Buchbinder,N.,Naor,J.S.,Schwartz,R.:Simplexpartitioningviaexponentialclocksandthemultiway cut problem. In:Proceedings of the forty-fifth annual ACM symposium on Theory of computing, ACM, pp. 535-544(2013)
[16] Sharma, A., Vondrák, J.:Multiway cut, pairwise realizable distributions, and descending thresholds. In:Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, pp. 724-733(2014)
[17] Langberg, M., Rabani. Y., Swamy, C.:Approximation algorithms for graph homomorphism problems. In:Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 176-187. Springer, Berlin (2006)
[18] Chekuri, C., Ene, A.:Submodular cost allocation problem and applications. In:Automata, Languages and Programming, pp 354-366. Springer, Berlin (2011)
[19] Lehmann, B., Lehmann, D., Nisan, N.:Combinatorial auctions with decreasing marginal utilities. In:Proceedings of the 3rd ACM conference on Electronic Commerce, ACM, pp. 18-28(2001)
[20] Feige, U., Vondrak, J.:The allocation problem with submodular utility functions. In:Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (2006)
[21] Dobzinski, S., Schapira, M.:An improved approximation algorithm for combinatorial auctions with submodular bidders. In:Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, Society for Industrial and Applied Mathematics, pp 1064-1073(2006)
[22] Feige, U.:On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39, 122-142(2009)
[23] Khot, S., Lipton, R.J., Markakis, E., Mehta, A.:Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica 52, 3-18(2008)
[24] Garey,M.R.,Johnson,D.S.:ComputersandIntractability:AGuidetotheTheoryofNP-Completeness. W. H. Freeman and Company, San Francisco (1979)
[25] Vondrák,J.:Symmetryandapproximabilityofsubmodularmaximizationproblems.SIAMJ.Comput. 42, 265-304(2013)
[26] Brooks, R.L.:On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37, 194-197(1941)
[27] Lovász, L.:Three short proofs in graph theory. J. Comb. Theory Ser. B 19(3), 269-271(1975)
[28] Austrin, P., Khot, S., Safra, M.:Inapproximability of vertex cover and independent set in bounded degree graphs. In:24th Annual IEEE Conference on Computational Complexity, pp 74-80(2009)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016