Combination can be hard: approximability of the unique coverage problem

ABSTRACT

We prove semi-logarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. Specifically, we prove O(1/ log^σ(ε)n) inapproximability assuming that NP ⊈ BPTIME(2^nε) for some ε > 0. We also prove O(1/log^1/3-ε n) inapproximability, for any ε > 0, assuming that refuting random instances of 3SAT is hard on average; and prove O(1/log n) inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an Ω(1/log n)-approximation algorithm as well as an Ω(1/log B)-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We describe how the (budgeted) unique coverage problem, motivated by real-world applications, has close connections to other theoretical problems including max cut, maximum coverage, and radio broad-casting.

REFERENCES

• 1: G. Aggarwal, T. Feder, R. Motwani, and A. Zhu, Algorithms for multi-product pricing, in Proc. 31st International Colloq. Automata, Languages and Programming, vol. 3142 of Lecture Notes in Computer Science, 2004, pp. 72--83.
• 2: Paola Alimonti , Viggo Kann, Hardness of Approximating Problems on Cubic Graphs, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.288-298, March 12-14, 1997
• 3: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 4: C. Ambühl, A. E. F. Clementi, M. D. Ianni, N. Levtov, A. Monti, D. Peleg, G. Rossi, and R. Silvestri, Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks, in Proc. 21st Annual Sympos. The-oretical Aspects of Computer Science, vol. 2996 of Lecture Notes in Computer Science, February 2004, pp. 418--427.
• 5: Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060632]
• 6: Aaron Archer , Christos Papadimitriou , Kunal Talwar , Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 7: V. Bahl, M. Hajiaghayi, K. Jain, V. S. Mirrokni, L. Qui, and A. Saberi, Cell breathing in wireless lan: Algorithms and evaluation. Manuscript, 2005.
• 8: Nikhil Bansal , Avrim Blum , Shuchi Chawla , Adam Meyerson, Approximation algorithms for deadline-TSP and vehicle routing with time-windows, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007385]
• 9: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 10: I. Chlamtac and O. Weinstein, The wave expansion approach to broadcasting in multi-hop radio networks, IEEE Transactions on Communications, 39 (1991).
• 11: Julia Chuzhoy , Sudipto Guha , Eran Halperi , Sanjeev Khanna , Guy Kortsarz , Joseph (Seffi) Nao, Asymmetric k-center is log^* n-hard to approximate, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007363]
• 12: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 13: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 14: Michael Elkin , Guy Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509972]
• 15: M. Elkin and G. Kortsarz, Polylogarithmic inapproximability of the radio broadcast problem, in Proc. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004, pp. 105--116.
• 16: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 17: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 18: Uriel Feige , Magnús M. Halldórsson , Guy Kortsarz , Aravind Srinivasan, Approximating the Domatic Number, SIAM Journal on Computing, v.32 n.1, p.172-195, 2003 [doi>10.1137/S0097539700380754]
• 19: Y. Fukuda, T. Abe, and Y. Oie, Decentralized access point selection architecture for wireless lans - deployability and robustness for wireless lans, in In Proc. of IEEE VTC, September 2004.
• 20: Leszek Gasieniec , David Peleg , Qin Xin, Faster communication in known topology radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073840]
• 21: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 22: Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Journal of Algorithms, v.31 n.1, p.228-248, April 1999 [doi>10.1006/jagm.1998.0993]
• 23: F. Gul and E. Stacchetti, Walrasian equilibrium with gross substitutes, Journal of Economic Theory, 87 (1999), pp. 95--124.
• 24: Venkatesan Guruswami , Jason D. Hartline , Anna R. Karlin , David Kempe , Claire Kenyon , Frank McSherry, On profit-maximizing envy-free pricing, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 25: V. Guruswami and L. Trevisan, The complexity of making unique choices: Approximating 1-in-k SAT, in Proc. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Vol. 3624 of Lecture Notes in Computer Science, 2005, pp. 99--110.
• 26: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 27: Dorit S. Hochbaum, Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 28: G. Judd and P. Steenkiste, Fixing 802.11 access point selection, in ACM SIGCOMM Poster, August 2002.
• 29: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
• 30: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.73-82, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872045]
• 31: D. R. Kowalski and A. Pelc, Centralized deterministic broadcasting in undirected multi-hop radio networks, in Proc. 7th International Work-shop on Approximation Algorithms for Combinatorial Optimization Problems, 2004, pp. 171--182.
• 32: Dariusz R. Kowalski , Andrzej Pelc, Time of Deterministic Broadcasting in Radio Networks with Local Knowledge, SIAM Journal on Computing, v.33 n.4, p.870-891, 2004 [doi>10.1137/S0097539702419339]
• 33: Eyal Kushilevitz , Yishay Mansour, An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks, SIAM Journal on Computing, v.27 n.3, p.702-712, June 1998 [doi>10.1137/S0097539794279109]
• 34: Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
• 35: Nissan Lev-Tov , David Peleg, Exact Algorithms and Approximation Schemes for Base Station Placement Problems, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.90-99, July 03-05, 2002
• 36: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 37: Anna Moss , Yuval Rabani, Approximation algorithms for constrained for constrained node weighted steiner tree problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.373-382, July 2001, Hersonissos, Greece [doi>10.1145/380752.380826]
• 38: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 39: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 40: C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, 43 (1991), pp. 425--440.
• 41: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 42: M. R. Salavatipour and J. Verstraete, Disjoint cycles: Integrality gap, hardness, and approximation, in Proc. 11th Conference on Integer Programming and Combinatorial Optimization, 2005, pp. 51--65.
• 43: L. Walras, Elements of Pure Economics, Allen and Unwin, 1954.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Theory