Lossy kernelization. (English) Zbl 1370.68136
Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 224-237 (2017).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W25 | Approximation algorithms |
References:
| [1] | Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-Coding. J. ACM 42, 4 (1995), 844-856. 10.1145/210332.210337 · Zbl 0885.68116 |
| [2] | Esther M. Arkin, Magnús M. Halldórsson, and Refael Hassin. 1993. Approximating the Tree and Tour Covers of a Graph. Inf. Process. Le. 47, 6 (1993), 275-282. 10.1016/0020-0190(93)90072-H · Zbl 0785.68041 |
| [3] | Sanjeev Arora, Boaz Barak, and David Steurer. 2015. Subexponential Algorithms for Unique Games and Related Problems. J. ACM 62, 5 (2015), 42. 10.1145/2775105 · Zbl 1426.05159 |
| [4] | Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. 2009. On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 8 (2009), 423-434. 10.1016/j.jcss.2009.04.001 · Zbl 1192.68288 |
| [5] | Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. 2011. Cross-Composition: A New Technique for Kernelization Lower Bounds. In 28th International Symposium on eoretical Aspects of Computer Science (STACS). 165- 176. · Zbl 1230.68085 |
| [6] | Hans L. Bodlaender, Stéphan omassé, and Anders Yeo. 2011. Kernel bounds for disjoint cycles and disjoint paths. eor. Comput. Sci. 412, 35 (2011), 4570- 4578. 10.1016/j.tcs.2011.04.039 · Zbl 1221.68099 |
| [7] | Al Borchers and Ding-Zhu Du. 1997. e k-Steiner Ratio in Graphs. SIAM J. Comput. 26, 3 (1997), 857-869. 10.1137/S0097539795281086 · Zbl 0870.68109 |
| [8] | Jaroslaw Byrka, Fabrizio Grandoni, omas Rothvoß, and Laura Sanità. 2013. Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM 60, 1 (2013), 6. 10.1145/2432622.2432628 · Zbl 1281.68234 |
| [9] | Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. · Zbl 1334.90001 |
| [10] | Holger Dell and Dániel Marx. 2012. Kernelization of packing problems. In Proceedings of the Twenty-ird Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012. 68-81. · Zbl 1421.68072 |
| [11] | Holger Dell and Dieter van Melkebeek. 2010. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In Proceedings of the 42nd ACM Symposium on eory of Computing, STOC 2010, Cambridge, Massachuses, USA, 5-8 June 2010. 251-260. 10.1145/1806689.1806725 · Zbl 1293.68132 |
| [12] | Irit Dinur and Samuel Safra. 2005. On the hardness of approximating minimum vertex cover. Annals of mathematics (2005), 439-485. · Zbl 1084.68051 |
| [13] | Michael Dom, Daniel Lokshtanov, and Saket Saurabh. 2014. Kernelization Lower Bounds rough Colors and IDs. ACM Transactions on Algorithms 11, 2 (2014), 13:1-13:20. 10.1145/2650261 · Zbl 1398.68226 |
| [14] | Rodney G Downey and Michael Ralph Fellows. 2012. Parameterized complexity. Springer Science & Business Media. |
| [15] | S. E. Dreyfus and R. A. Wagner. 1971. e steiner problem in graphs. Networks 1, 3 (1971), 195-207. STOC’17, June 2017, Montreal, Canada Lokshtanov et al. · Zbl 0229.05125 |
| [16] | Andrew Drucker. 2015. New Limits to Classical and antum Instance Compression. SIAM J. Comput. 44, 5 (2015), 1443-1479. · Zbl 1330.68092 |
| [17] | Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Hadas Shachnai. 2013. Tractable Parameterizations for the Minimum Linear Arrangement Problem. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings. 457-468. · Zbl 1394.68441 |
| [18] | Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, and Hadas Shachnai. 2012. Parameterized Approximation via Fidelity Preserving Transformations. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I. 351-362. 10.1007/978-3-642-31594-7_30 · Zbl 1272.68459 |
| [19] | Lance Fortnow and Rahul Santhanam. 2011. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77, 1 (2011), 91-106. 10.1016/j.jcss.2010.06.007 · Zbl 1233.68144 |
| [20] | Zachary Friggstad and Mohammad R. Salavatipour. 2011. Approximability of Packing Disjoint Cycles. Algorithmica 60, 2 (2011), 395-400. · Zbl 1213.05245 |
| [21] | Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. 2015. A Completeness eory for Polynomial (Turing) Kernelization. Algorithmica 71, 3 (2015), 702-730. 10.1007/s00453-014-9910-8 · Zbl 1312.68102 |
| [22] | Danny Hermelin and Xi Wu. 2012. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the Twenty-ird Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012. 104-113. · Zbl 1421.68086 |
| [23] | Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci. 63, 4 (2001), 512-530. 10.1006/jcss.2001.1774 · Zbl 1006.68052 |
| [24] | David R. Karger, Rajeev Motwani, and G. D. S. Ramkumar. 1997. On Approximating the Longest Path in a Graph. Algorithmica 18, 1 (1997), 82-98. · Zbl 0876.68083 |
| [25] | Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on eory of Computing, May 19-21, 2002, Montréal, ébec, Canada. 767-775. 10.1145/509907.510017 · Zbl 1192.68367 |
| [26] | Subhash Khot and Oded Regev. 2008. Vertex cover might be hard to approximate to within 2- ε. J. Comput. System Sci. 74, 3 (2008), 335-349. 10.1016/j.jcss.2007.06.019 · Zbl 1133.68061 |
| [27] | Stefan Kratsch. 2014. Recent developments in kernelization: A survey. Bulletin of the EATCS 113 (2014). · Zbl 1409.68144 |
| [28] | Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Kernelization– preprocessing with a guarantee. In e Multivariate Algorithmic Revolution and Beyond. Springer, 129-161. · Zbl 1358.68141 |
| [29] | Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. 2016. Lossy Kernelization. CoRR abs/1604.04111 (2016). http://arxiv.org/abs/1604. · Zbl 1370.68136 |
| [30] | 04111 |
| [31] | Dániel Marx. 2008. Parameterized Complexity and Approximation Algorithms. Comput. J. 51, 1 (2008), 60-78. 10.1093/comjnl/bxm048 · Zbl 1146.05314 |
| [32] | Dana Moshkovitz. 2015. e Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover. eory of Computing 11 (2015), 221-235. · Zbl 1335.68097 |
| [33] | Jelani Nelson. 2007. A Note on Set Cover Inapproximability Independent of Universe Size. Electronic Colloquium on Computational Complexity (ECCC) 14, 105 (2007). |
| [34] | Mohammad R. Salavatipour and Jacques Verstraëte. 2005. Disjoint Cycles: Integrality Gap, Hardness, and Approximation. In Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, Proceedings. 51-65. 10.1007/11496915_5 · Zbl 1119.05103 |
| [35] | Carla D. Savage. 1982. Depth-First Search and the Vertex Cover Problem. Inf. Process. Le. 14, 5 (1982), 233-237. · Zbl 0498.68041 |
| [36] | Michael Sipser. 2012. Introduction to the eory of Computation. Cengage Learning. |
| [37] | David P. Williamson and David B. Shmoys. 2011. e Design of Approximation Algorithms. Cambridge University Press. · Zbl 1219.90004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
