Cited By
View all- Bansal NCharikar MCohen E(2019)On a generalization of iterated and randomized roundingProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316313(1125-1135)Online publication date: 23-Jun-2019
The entropy rounding method in approximation algorithms
Pages 356 - 372
Abstract
Let A be a matrix, c be any linear objective function and x be a fractional vector, say an LP solution to some discrete optimization problem. Then a recurring task in theoretical computer science (and in approximation algorithms in particular) is to obtain an integral vector y such that Ax ≈ Ay and cTy exceeds cTx by only a moderate factor.
We give a new randomized rounding procedure for this task, provided that A has bounded Δ-approximate entropy. This property means that for uniformly chosen random signs χ(j) ε {±1} on any subset of the columns, the outcome Aχ can be approximately described using at most m/5 bits in expectation (with m being the number of selected columns).
To achieve this result, we modify well-known techniques from the field of discrepancy theory, especially we rely on Beck's entropy method, which to the best of our knowledge has never been used before in the context of approximation algorithms. Our result can be made constructive using the Bansal framework based on semidefinite programming.
We demonstrate the versatility of our procedure by rounding fractional solutions to column-based linear programs for some generalizations of Bin Packing. For example we obtain a polynomial time OPT + O(log2 OPT) approximation for Bin Packing With Rejection and the first AFPTAS for the Train Delivery problem.
References
[1]
{AGM+10} A. Asadpour, M. X. Goemans, A. Madry, S. O. Gharan, and A. Saberi. An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem. In Moses Charikar, editor, SODA. pages 379--389. SIAM, 2010.
[2]
{AS08} N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., Hoboken, NJ, third edition, 2008. With an appendix on the life and work of Paul Erdőős.
[3]
{Ban98} W. Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures Algorithms, 12(4):351--360, 1998.
[4]
{Ban10} N. Bansal. Constructive algorithms for discrepancy minimization. In FOCS, pages 3--10, 2010.
[5]
{BCH08} W. Bein, J. R. Correa, and X. Han. A fast asymptotic approximation scheme for bin packing with rejection. Theoret. Comput. Sci., 393(1--3):14--22, 2008.
[6]
{BF81} J. Beck and T. Fiala. "Integer-making" theorems. Discrete Appl. Math., 3(1):1--8, 1981.
[7]
{BGRS10} J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. An improved LP-based approximation for Steiner tree. In Leonard J. Schulman, editor, STOC, pages 583--592. ACM, 2010.
[8]
{CGJ84} E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation algorithms for bin-packing---an updated survey. In Algorithm design for computer system design, volume 284 of CISM Courses and Lectures, pages 49--106. Springer, Vienna, 1984.
[9]
{CVZ10} C. Chekuri, J. Vondrák, and R. Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS, pages 575--584, 2010.
[10]
{CVZ11} C. Chekuri, J. Vondrák, and R. Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In SODA, pages 1080--1097, 2011.
[11]
{DH06} G. Dósa and Y. He. Bin packing problems with rejection penalties and their dual problems. Inf. Comput., 204:795--815, May 2006.
[12]
{DMM10} A. Das, C. Mathieu, and S. Mozes. The train delivery problem- vehicle routing meets bin packing. In 8th Workshop on Approximation and Online Algorithms (WAOA'10), pages 94--105, 2010.
[13]
{DS03} B. Doerr and A. Srivastav. Multicolour discrepancies. In Combinatorics, Probability and Computing, Cambridge University Press, volume 12. 2003.
[14]
{Eis57} K. Eisemann. The trim problem. Management Science, 3(3):279--284, 1957.
[15]
{EKRS11} F. Eisenbrand, N. Kakimura, T. Rothvoß, and L. Sanità. Set covering with ordered replacement - additive and multiplicative gaps. In Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011, 2011.
[16]
{EL08} L. Epstein and A. Levin. An APTAS for generalized cost variable-sized bin packing. SIAM Journal on Computing, 38(1):411--428, 2008.
[17]
{EL09} L. Epstein and A. Levin. AFPTAS results for common variants of bin packing: A new method to handle the small items. CoRR, abs/0906.5050, 2009.
[18]
{EL10} L. Epstein and A. Levin. AFPTAS results for common variants of bin packing: A new method for handling the small items. SIAM Journal on Optimization. 20(6):3121--3145, 2010.
[19]
{Eps06} L. Epstein. Bin packing with rejection revisited. In Approximation and online algorithms, volume 4368 of Lecture Notes in Comput. Sci., pages 146--159. Springer, Berlin, 2006.
[20]
{Eps10} L. Epstein. Bin packing with rejection revisited. Algorithmica, 56(4):505--528, 2010.
[21]
{FdlVL81} W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1 + ε in linear time. Combinatorica, 1(4):349--355, 1981.
[22]
{Fei08} U. Feige. On allocations that maximize fairness. In Shang-Hua Teng, editor, SODA, pages 287--293. SIAM, 2008.
[23]
{GG61} P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Operations Research, 9:849--859, 1961.
[24]
{GJ79} M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, New York, 1979.
[25]
{GKPS06} R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324--360, 2006.
[26]
{GLS81} M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169--197, 1981.
[27]
{Goe97} M. X. Goemans. Semidefinite programming in combinatorial optimization. Mathematical Programming, 79:143--161, 1997.
[28]
{GW04} M. X. Goemans and D. P. Williamson. Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. J. Comput. System Sci., 68(2):442--470, 2004.
[29]
{HSS10} B. Haeupler, B. Saha, and A. Srinivasan. New constructive aspects of the lovasz local lemma. CoRR, abs/1001.1231, 2010.
[30]
{Jai98} K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 448--457, 1998.
[31]
{JDU+74} D. S. Johnson, A. Demers, J. D. Ullman, M. R Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299--325, 1974.
[32]
{Joh73} D. S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973.
[33]
{Joh85} David S. Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 6:434--451, 1985.
[34]
{KK82} N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982), pages 312--320. IEEE, New York, 1982.
[35]
{Kle66} D. Kleitman. On a combinatorial problem of Erdős. Proc. Amer. Math. Soc., 17:139--141, 1966.
[36]
{KLR+87} R M. Karp, F. T. Leighton, R L. Rivest, C. D. Thompson, U. V. Vazirani, and V. V. Vazirani. Global wire routing in two-dimensional arrays. Algorithmica, 2(1):113--129, 1987.
[37]
{KMS98} D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246--265, 1998.
[38]
{KV02} B. Korte and J. Vygen. Combinatorial Optimization - Theory and Algorithms. Springer-Verlag, Second Edition, 2002.
[39]
{Lov03} L. Lovász. Semidefinite programs and combinatorial optimization. In Bruce A. Reed and Cláudia L. Sales, editors, Recent Advances in Algorithms and Combinatorics, volume 11 of CMS Books in Mathematics, pages 137--194. Springer-Verlag, Berlin-Heidelberg-New York-Hong Kong-London-Milan-Paris-Tokyo, 2003.
[40]
{LRS11} L. C. Lau, R. Ravi, and M. Singh. Iterative methods in combinatorial optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, New York, 2011.
[41]
{LST87} J. K. Lenstra, D. B. Shmoys, and E. Tardos. Approximation algorithms for scheduling unrelated parallel machines. In Ashok K. Chandra, editor, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 217--224, Los Angeles, CA, October 1987. IEEE Computer Society Press.
[42]
{LSV86} L. Lovász, J. Spencer, and K. Vesztergombi. Discrepancy of set-systems and matrices. European J. Combin., 7(2):151--160, 1986.
[43]
{Mat99} J. Matoušek. Geometric discrepancy, volume 18 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1999. An illustrated guide.
[44]
{MU05} M. Mitzenmacher and E. Upfal. Probability and computing. Cambridge University Press, Cambridge, 2005. Randomized algorithms and probabilistic analysis.
[45]
{Mur87} F. Murgolo. An efficient approximation scheme for variable-sized bin packing. SIAM J. Comput., 16:149--161, February 1987.
[46]
{PST95} S. A. Plotkin, D. B. Shmoys, and É. Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 20(2):257--301, 1995.
[47]
{Ram95} M. Ramana. An exact duality theory for semidefinite programming and its complexity implications. Mathematical Programming, 77, 1995.
[48]
{RT87} P. Raghavan and C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365--374, 1987.
[49]
{Spe85} J. Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society, 289(2):679--706, 1985.
[50]
{Sri97} A. Srinivasan. Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), pages 692--701, New York, 1997. ACM.
[51]
{SST} J. H. Spencer, A. Srinivasan, and P. Tetali. The discrepancy of permutation families. Unpublished manuscript.
[52]
{Vaz01} V. Vazirani. Approximation algorithms. Springer-Verlag, Berlin, 2001.
[53]
{WS11} D. Williamson and D. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
[54]
{ZMO07} A. Zhu, R. Motwani, and L. O'Callaghan. Asymptotic Polynomial-Time Approximation Schemes. Chapman and Hall/CRC, 2011/02/28 2007.
Index Terms
- The entropy rounding method in approximation algorithms
Recommendations
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs
Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-...
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs
Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial OptimizationKarloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-...
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2012
1764 pages
Sponsors
- Kyoto University: Kyoto University
In-Cooperation
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 17 January 2012
Check for updates
Qualifiers
- Research-article
Conference
SODA '12
Sponsor:
- Kyoto University
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 168Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
Cited By
View all- Bansal NCharikar MCohen E(2019)On a generalization of iterated and randomized roundingProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316313(1125-1135)Online publication date: 23-Jun-2019
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in