Document Open Access Logo

Approximation in (Poly-) Logarithmic Space

Authors Arindam Biswas , Venkatesh Raman , Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.16.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Arindam Biswas
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Venkatesh Raman
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Bergen, Norway

Cite As Get BibTex

Arindam Biswas, Venkatesh Raman, and Saket Saurabh. Approximation in (Poly-) Logarithmic Space. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.16

Abstract

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time n^{O(d² + (d / ε))}, uses O(d² + (d / ε) log n) bits of space, and achieves an approximation ratio of O((d / ε) n^ε) for any positive ε ≤ 1 and any constant d ∈ ℕ. In particular, this yields a factor-O(d log n) approximation algorithm which uses O(log² n) bits of space. As a corollary, we obtain similar bounds on space and approximation ratio for Vertex Cover and several graph deletion problems. For graphs with maximum degree Δ, one can do better. We give a factor-2 approximation algorithm for Vertex Cover which runs in time n^{O(Δ)} and uses O(Δ log n) bits of space.
For Independent Set on graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O(log n) bits of space. We also devise a factor-O(d²) approximation algorithm for Dominating Set on d-degenerate graphs which runs in time n^{O(log n)} and uses O(log² n) bits of space. For d-regular graphs, we observe that a known randomized algorithm which achieves an approximation ratio of O(log d) can be derandomized to run in polynomial time and use O(log n) bits of space.
Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • approximation
  • logspace
  • logarithmic
  • log
  • space
  • small
  • limited
  • memory
  • ROM
  • read-only

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Eric Allender and Meena Mahajan. The complexity of planarity testing. Information and Computation, 189(1):117-134, February 2004. URL: https://doi.org/10.1016/j.ic.2003.09.002.
  2. Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms, 2(2):153-177, April 2006. URL: https://doi.org/10.1145/1150334.1150336.
  3. Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley, Hoboken, NJ, USA, third edition, 2008. Google Scholar
  4. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory of Computing, 7(1):27-43, March 2011. URL: https://doi.org/10.4086/toc.2011.v007a003.
  5. Paul Beame. A general Sequential Time-Space Tradeoff for Finding Unique Elements. SIAM Journal on Computing, 20(2):270-277, April 1991. URL: https://doi.org/10.1137/0220017.
  6. Ioana O. Bercea, Navin Goyal, David G. Harris, and Aravind Srinivasan. On Computing Maximal Independent Sets of Hypergraphs in Parallel. ACM Transactions on Parallel Computing, 3(1):1-13, January 2017. URL: https://doi.org/10.1145/2938436.
  7. Bonnie Berger, John Rompel, and Peter W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. Journal of Computer and System Sciences, 49(3):454-477, December 1994. URL: https://doi.org/10.1016/S0022-0000(05)80068-6.
  8. Allan Borodin and Stephen A. Cook. A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM Journal on Computing, 11(2):287-297, May 1982. URL: https://doi.org/10.1137/0211022.
  9. Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, and Martin Tompa. A time-space tradeoff for sorting on non-oblivious machines. Journal of Computer and System Sciences, 22(3):351-364, June 1981. URL: https://doi.org/10.1016/0022-0000(81)90037-4.
  10. Jonathan F. Buss and Judy Goldsmith. Nondeterminism within P. SIAM Journal on Computing, 22(3):560-572, June 1993. URL: https://doi.org/10.1137/0222038.
  11. Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows. Advice classes of parameterized tractability. Annals of Pure and Applied Logic, 84(1):119-138, March 1997. URL: https://doi.org/10.1016/S0168-0072(95)00020-8.
  12. J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, April 1979. URL: https://doi.org/10.1016/0022-0000(79)90044-8.
  13. Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms. In 26th Annual European Symposium on Algorithms, volume 112, pages 13:1 - 13:16, Helsinki, Finland, August 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/lipics.esa.2018.13.
  14. Siu On Chan. Approximation Resistance from Pairwise-Independent Subgroups. Journal of the ACM, 63(3):1-32, September 2016. URL: https://doi.org/10.1145/2873054.
  15. Timothy M. Chan, J. Ian Munro, and Venkatesh Raman. Selection and Sorting in the "Restore" Model. ACM Transactions on Algorithms, 14(2):1-18, June 2018. URL: https://doi.org/10.1145/3168005.
  16. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer-Verlag, Cham, Switzerland, 2015. Google Scholar
  17. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the 46th Annual Symposium on Theory of Computing, pages 624-633, New York, NY, USA, May 2014. ACM Press. URL: https://doi.org/10.1145/2591796.2591884.
  18. Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the 46th Annual Symposium on Theory of Computing, pages 383-392, New York, NY, USA, May 2014. ACM Press. URL: https://doi.org/10.1145/2591796.2591865.
  19. Stefan Fafianie and Stefan Kratsch. A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time. In Mathematical Foundations of Computer Science, volume 9235, pages 299-310, Milan, Italy, August 2015. Springer-Verlag. URL: https://doi.org/10.1007/978-3-662-48054-0_25.
  20. Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. Journal of Computer and System Sciences, 34(1):19-26, February 1987. URL: https://doi.org/10.1016/0022-0000(87)90002-X.
  21. Johan Håstad. Clique is hard to approximate within n^(1 - ε). Acta Mathematica, 182(1):105-142, March 1999. URL: https://doi.org/10.1007/BF02392825.
  22. Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Ondřej Suchý. Parameterized Complexity of Directed Steiner Tree on Sparse Graphs. SIAM Journal on Discrete Mathematics, 31(2):1294-1327, January 2017. URL: https://doi.org/10.1137/15M103618X.
  23. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2 - ε. Journal of Computer and System Sciences, 74(3):335-349, May 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.019.
  24. Jason Li and Ryan O'Donnell. Bounding Laconic Proof Systems by Solving CSPs in Parallel. In Proceedings of the 29th Annual Symposium on Parallelism in Algorithms and Architectures, pages 95-100, Washington, DC, USA, July 2017. ACM Press. URL: https://doi.org/10.1145/3087556.3087557.
  25. Michael Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15(4):1036-1053, November 1986. URL: https://doi.org/10.1137/0215074.
  26. Michael Luby and Noam Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the 25th Annual Smposium on Theory of Computing, pages 448-457, San Diego, CA, USA, May 1993. ACM Press. URL: https://doi.org/10.1145/167088.167211.
  27. Andrew McGregor. Graph stream algorithms: A survey. ACM SIGMOD Record, 43(1):9-20, May 2014. URL: https://doi.org/10.1145/2627692.2627694.
  28. J. Ian Munro and Michael S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315-323, November 1980. URL: https://doi.org/10.1016/0304-3975(80)90061-4.
  29. J. Ian Munro and Venkatesh Raman. Selection from read-only memory and sorting with minimum data movement. Theoretical Computer Science, 165(2):311-323, October 1996. URL: https://doi.org/10.1016/0304-3975(95)00225-1.
  30. Rasmus Pagh and Jakob Pagter. Optimal time-space trade-offs for non-comparison-based sorting. In Proceedings of the 13th Annual Symposium on Discrete Algorithms, pages 9-18, Philadelphia, PA, USA, January 2002. SIAM. URL: https://doi.org/10.5555/545381.545383.
  31. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 264-268, Palo Alto, CA, USA, November 1998. IEEE Comput. Soc. Press. URL: https://doi.org/10.1109/SFCS.1998.743455.
  32. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms, 9(1):1-23, December 2012. URL: https://doi.org/10.1145/2390176.2390187.
  33. Valentin Polishchuk and Jukka Suomela. A simple local 3-approximation algorithm for vertex cover. Information Processing Letters, 109(12):642-645, May 2009. URL: https://doi.org/10.1016/j.ipl.2009.02.017.
  34. Venkatesh Raman and Sarnath Ramnath. Improved upper bounds for time-space trade-offs for selection. Nordic Journal of Computing, 6(2):162-180, June 1999. URL: https://doi.org/10.5555/762350.762354.
  35. Venkatesh Raman and Saket Saurabh. Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles. Algorithmica, 52(2):203-225, October 2008. URL: https://doi.org/10.1007/s00453-007-9148-9.
  36. John H. Reif. Symmetric Complementation. Journal of the ACM, 31(2):401-421, March 1984. URL: https://doi.org/10.1145/62.322436.
  37. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4):1-24, September 2008. URL: https://doi.org/10.1145/1391289.1391291.
  38. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, April 1970. URL: https://doi.org/10.1016/S0022-0000(70)80006-X.
  39. Maria Serna. Approximating linear programming is log-space complete for P. Information Processing Letters, 37(4):233-236, February 1991. URL: https://doi.org/10.1016/0020-0190(91)90194-M.
  40. Till Tantau. Logspace Optimization Problems and Their Approximability Properties. Theory of Computing Systems, 41(2):327-350, August 2007. URL: https://doi.org/10.1007/s00224-007-2011-1.
  41. Luca Trevisan. Parallel Approximation Algorithms by Positive Linear Programming. Algorithmica, 21(1):72-88, May 1998. URL: https://doi.org/10.1007/PL00009209.
  42. Luca Trevisan and Fatos Xhafa. The Parallel Complexity of Positive Linear Programming. Parallel Processing Letters, 08(04):527-533, December 1998. URL: https://doi.org/10.1142/S0129626498000511.
  43. Heribert Vollmer. Introduction to Circuit Complexity. Springer-Verlag, Berlin, Germany, 1999. Google Scholar
  44. Tomoyuki Yamakami. Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems. In Combinatorial Optimization and Applications, volume 8287, pages 318-329, Chengdu, China, December 2013. Springer-Verlag. URL: https://doi.org/10.1007/978-3-319-03780-6_28.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact