Document Open Access Logo

A Structural Investigation of the Approximability of Polynomial-Time Problems

Authors Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2022.30.pdf
  • Filesize: 0.77 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Classification Theorems
  • Hardness of Approximation in P
  • Fine-grained Complexity Theory

Metrics

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

Abstract

An extensive research effort targets optimal (in)approximability results for various NP-hard optimization problems. Notably, the works of (Creignou'95) as well as (Khanna, Sudan, Trevisan, Williamson'00) establish a tight characterization of a large subclass of MaxSNP, namely Boolean MaxCSPs and further variants, in terms of their polynomial-time approximability. Can we obtain similarly encompassing characterizations for classes of polynomial-time optimization problems?
To this end, we initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of k-XOR and Maximum k-Cover). Specifically, for each k, MaxSP_k denotes the class of O(m^k)-time problems of the form max_{x_1,… , x_k} #{y : ϕ(x_1,… ,x_k,y)} where ϕ is a quantifier-free first-order property and m denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and exact Max-3-SAT}, we show that for any MaxSP_k problem definable by a quantifier-free m-edge graph formula φ, the best possible approximation guarantee in faster-than-exhaustive-search time O(m^{k-δ})falls into one of four categories:
- optimizable to exactness in time O(m^{k-δ}),
- an (inefficient) approximation scheme, i.e., a (1+ε)-approximation in time O(m^{k-f(ε)}),
- a (fixed) constant-factor approximation in time O(m^{k-δ}), or
- a nm^ε-approximation in time O(m^{k-f(ε)}).
We obtain an almost complete characterization of these regimes, for MaxSP_k as well as for an analogously defined minimization class MinSP_k. As our main technical contribution, we show how to rule out the existence of approximation schemes for a large class of problems admitting constant-factor approximations, under a hypothesis for exact Sparse Max-3-SAT algorithms posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we observe: (1) Exact optimizability has a simple algebraic characterization, (2) only few maximization problems do not admit a constant-factor approximation; these do not even have a subpolynomial-factor approximation, and (3) constant-factor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.

Cite As Get BibTex

Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. A Structural Investigation of the Approximability of Polynomial-Time Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.30

Author Details

Karl Bringmann
  • Universität des Saarlandes, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Alejandro Cassis
  • Universität des Saarlandes, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Nick Fischer
  • Universität des Saarlandes, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Marvin Künnemann
  • TU Kaiserslautern, Germany

Funding

Karl Bringmann, Alejandro Cassis, Nick Fischer: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979). Marvin Künnemann: Part of this research was performed at ETH Zürich, Institute for Theoretical Studies, supported by Dr. Max Rössler, by the Walter Haefner Foundation, and by the ETH Zürich Foundation.

References

  1. Amir Abboud and Arturs Backurs. Towards hardness of approximation for polynomial time problems. In Proceedings of the 8th Conference on Innovations in Theoretical Computer Science, volume 67 of ITCS '17, pages 11:1-11:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS '15, pages 59-78. IEEE Computer Society, 2015. Google Scholar
  3. Amir Abboud and Aviad Rubinstein. Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, volume 94 of ITCS '18, pages 35:1-35:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  4. Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS '17, pages 25-36. IEEE Computer Society, 2017. Google Scholar
  5. Josh Alman, Timothy Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS '16, pages 467-476. IEEE Computer Society, 2016. Google Scholar
  6. Josh Alman, Timothy Chan, and Ryan Williams. Faster deterministic and Las Vegas algorithms for offline approximate nearest neighbors in high dimensions. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pages 637-649. SIAM, 2020. Google Scholar
  7. Josh Alman and Virginia Vassilevska Williams. OV graphs are (probably) hard instances. In Proceedings of the 11th Conference on Innovations in Theoretical Computer Science, volume 151 of ITCS '20, pages 83:1-83:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  8. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '21, pages 522-539. SIAM, 2021. Google Scholar
  9. Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In Proceedings of the 47th IEEE Annual Symposium on Foundations of Computer Science, FOCS '06, pages 459-468. IEEE Computer Society, 2006. Google Scholar
  10. Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya P. Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 1018-1028. SIAM, 2014. Google Scholar
  11. Alexandr Andoni, Piotr Indyk, and Ilya P. Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathematicians, ICM '18, pages 3287-3318, 2018. Google Scholar
  12. Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Polylogarithmic approximation for edit distance and the asymmetric query complexity. In Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science, FOCS '10, pages 377-386. IEEE Computer Society, 2010. Google Scholar
  13. Alexandr Andoni and Negev Shekel Nosatzki. Edit distance in near-linear time: it’s a constant factor. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS '20, pages 990-1001. IEEE, 2020. Google Scholar
  14. Alexandr Andoni and Krzysztof Onak. Approximating edit distance in near-linear time. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC '09, pages 199-204. ACM, 2009. Google Scholar
  15. Alexandr Andoni and Ilya P. Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC '15, pages 793-801. ACM, 2015. Google Scholar
  16. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, STOC '18, pages 267-280. ACM, 2018. Google Scholar
  17. Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar. Approximating edit distance efficiently. In Proceedings of the 45th IEEE Annual Symposium on Foundations of Computer Science, FOCS '04, pages 550-559. IEEE Computer Society, 2004. Google Scholar
  18. Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami. A sublinear algorithm for weakly approximating edit distance. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC '03, pages 316-324. ACM, 2003. Google Scholar
  19. Tugkan Batu, Funda Ergün, and Süleyman Cenk Sahinalp. Oblivious string embeddings and edit distance approximations. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '06, pages 792-801. SIAM, 2006. Google Scholar
  20. Allan Borodin, Rafail Ostrovsky, and Yuval Rabani. Subquadratic approximation algorithms for clustering problems in high dimensional spaces. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, STOC '99, pages 435-444. ACM, 1999. Google Scholar
  21. Joshua Brakensiek and Aviad Rubinstein. Constant-factor approximation of near-linear edit distance in near-linear time. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, STOC '20, pages 685-698. ACM, 2020. Google Scholar
  22. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS '15, pages 661-670. IEEE Computer Society, 2014. Google Scholar
  23. Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. Fine-grained completeness for optimization in P. In APPROX-RANDOM, volume 207 of LIPIcs, pages 9:1-9:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  24. Karl Bringmann, Nick Fischer, and Marvin Künnemann. A fine-grained analogue of Schaefer’s theorem in P: Dichotomy of ∃^k∀-quantified first-order graph properties. In Proceedings of the 34th Computational Complexity Conference, volume 137 of CCC '19, pages 31:1-31:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  25. Karl Bringmann, Marvin Künnemann, and Karol Wegrzycki. Approximating APSP without scaling: Equivalence of approximate min-plus and exact min-max. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing, STOC '19, pages 943-954. ACM, 2019. Google Scholar
  26. Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael E. Saks. Approximating edit distance within constant factor in truly sub-quadratic time. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS '18, pages 979-990. IEEE Computer Society, 2018. Google Scholar
  27. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-ETH to FPT-inapproximability: Clique, dominating set, and more. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS '17, pages 743-754. IEEE Computer Society, 2017. Google Scholar
  28. Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. In Proceedings of the 33th Computational Complexity Conference, volume 102 of CCC '18, pages 14:1-14:45. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  29. Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, and Aviad Rubinstein. Fine-grained complexity meets IP = PSPACE. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 1-20. SIAM, 2019. Google Scholar
  30. Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 21-40. SIAM, 2019. Google Scholar
  31. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132 of ICALP '19, pages 42:1-42:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  32. Nadia Creignou. A dichotomy theorem for maximum generalized satisfiability problems. J. Comput. Syst. Sci., 51(3):511-522, 1995. Google Scholar
  33. Martin Dietzfelbinger, Philipp Schlag, and Stefan Walzer. A subquadratic algorithm for 3XOR. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, volume 117 of MFCS '18, pages 59:1-59:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  34. Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. J. ACM, 61(1):1:1-1:23, 2014. Google Scholar
  35. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. Google Scholar
  36. Andreas Emil Feldmann, C. S. Karthik, Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Electronic Colloquium on Computational Complexity (ECCC), 27:86, 2020. Google Scholar
  37. Harold N. Gabow. Scaling algorithms for network problems. J. Comput. Syst. Sci., 31(2):148-168, 1985. Google Scholar
  38. Jiawei Gao. On the fine-grained complexity of least weight subsequence in multitrees and bounded treewidth DAGs. In Proceedings of the 14th International Symposium on Parameterized and Exact Computation, volume 148 of IPEC '19, pages 16:1-16:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  39. Jiawei Gao and Russell Impagliazzo. The fine-grained complexity of strengthenings of first-order logic. Electronic Colloquium on Computational Complexity (ECCC), 26:9, 2019. Google Scholar
  40. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2):23:1-23:35, 2019. Google Scholar
  41. Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In Proceedings of the 25th International Conference on Very Large Data Bases, VLDB '99, pages 518-529. Morgan Kaufmann, 1999. Google Scholar
  42. Ashish Goel, Piotr Indyk, and Kasturi R. Varadarajan. Reductions among high dimensional proximity problems. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '01, pages 769-778. SIAM, 2001. Google Scholar
  43. Elazar Goldenberg, Aviad Rubinstein, and Barna Saha. Does preprocessing help in fast sequence comparisons? In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, STOC '20, pages 657-670. ACM, 2020. Google Scholar
  44. Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing, 8(1):321-350, 2012. Google Scholar
  45. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  46. Dorit S. Hochbaum. Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems, pages 94-143. PWS Publishing Co., 1996. Google Scholar
  47. Piotr Indyk. Dimensionality reduction techniques for proximity problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, pages 371-378. SIAM, 2000. Google Scholar
  48. Piotr Indyk. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '03, pages 539-545. SIAM, 2003. Google Scholar
  49. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC ’98, pages 604-613. ACM, 1998. Google Scholar
  50. Zahra Jafargholi and Emanuele Viola. 3SUM, 3XOR, triangles. Algorithmica, 74(1):326-343, 2016. Google Scholar
  51. C. S. Karthik, Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. J. ACM, 66(5):33:1-33:38, 2019. Google Scholar
  52. Karthik C. S. and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic. In Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, volume 124 of ITCS '19, pages 17:1-17:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  53. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The approximability of constraint satisfaction problems. SIAM J. Comput., 30(6):1863-1920, 2000. Google Scholar
  54. Donald E. Knuth. Dancing links. CoRR, abs/cs/0011047, 2000. URL: http://arxiv.org/abs/0011047.
  55. Michal Koucký and Michael E. Saks. Constant factor approximations to edit distance on far input pairs in nearly linear time. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, STOC '20, pages 699-712. ACM, 2020. Google Scholar
  56. Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt. Incremental string comparison. SIAM J. Comput., 27(2):557-582, 1998. Google Scholar
  57. Bingkai Lin. Constant approximating k-clique is w[1]-hard. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, STOC '21, pages 1749-1756. ACM, 2021. Google Scholar
  58. Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 1236-1252. SIAM, 2018. Google Scholar
  59. Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pages 62-81. SIAM, 2020. Google Scholar
  60. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425-440, 1991. Google Scholar
  61. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC '13, pages 515-524. ACM, 2013. Google Scholar
  62. Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, STOC '18, pages 1260-1268. ACM, 2018. Google Scholar
  63. Noah Stephens-Davidowitz and Vinod Vaikuntanathan. SETH-hardness of coding problems. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS '19, pages 287-301. IEEE Computer Society, 2019. Google Scholar
  64. Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. J. ACM, 62(2), 2015. Google Scholar
  65. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians, ICM '18, pages 3447-3487, 2018. Google Scholar
  66. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. Google Scholar
  67. Ryan Williams. Algorithms and resource requirements for fundamental problems. ProQuest LLC, Ann Arbor, MI, 2007. Thesis (Ph.D.)-Carnegie Mellon University. Google Scholar
  68. Ryan Williams. Faster decision of first-order graph properties. In Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ’14. ACM, 2014. Google Scholar
  69. Ryan Williams. On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 1207-1215. SIAM, 2018. Google Scholar
  70. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact