The Communication Complexity of Approximate Set Packing and Covering
- 25 June 2002
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 868-875
- https://doi.org/10.1007/3-540-45465-9_74
Abstract
No abstract availableThis publication has 9 references indexed in Scilit:
- On the distributional complexity of disjointnessPublished by Springer Nature ,2005
- An efficient approximate allocation algorithm for combinatorial auctionsPublished by Association for Computing Machinery (ACM) ,2001
- Truth revelation in approximately efficient combinatorial auctionsPublished by Association for Computing Machinery (ACM) ,1999
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Clique is hard to approximate within n1−εActa Mathematica, 1999
- On the hardness of approximating minimization problemsPublished by Association for Computing Machinery (ACM) ,1993
- Optima of dual integer linear programsCombinatorica, 1988
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975