Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
18 | Jean Cardinal, Raphael Steiner |
Inapproximability of shortest paths on perfect matching polytopes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2210.14608, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Andreas Galanis, Heng Guo 0001, Jiaheng Wang 0002 |
Inapproximability of Counting Hypergraph Colourings. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Theory ![In: ACM Trans. Comput. Theory 14(3-4), pp. 1-33, December 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Miroslav Chlebík, Janka Chlebíková |
Weighted amplifiers and inapproximability results for Travelling Salesman problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comb. Optim. ![In: J. Comb. Optim. 43(5), pp. 1368-1390, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee |
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pp. 1493-1530, 2022, SIAM, 978-1-61197-707-3. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Alexander Meiburg |
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pp. 58-68, 2022, IEEE, 978-1-6654-5519-0. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos |
Pure-Circuit: Strong Inapproximability for PPAD. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pp. 159-170, 2022, IEEE, 978-1-6654-5519-0. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos |
Constant inapproximability for PPA. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pp. 1010-1023, 2022, ACM, 978-1-4503-9264-8. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Karthik C. S., Subhash Khot |
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA., pp. 6:1-6:21, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-241-9. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
18 | Joshua Brakensiek, Venkatesan Guruswami |
The Quest for Strong Inapproximability Results with Perfect Completeness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Algorithms ![In: ACM Trans. Algorithms 17(3), pp. 27:1-27:35, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Timothée Martinod, Valentin Pollet, Benoît Darties, Rodolphe Giroudeau, Jean-Claude König |
Complexity and inapproximability results for balanced connected subgraph problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 886, pp. 69-83, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Sai Sandeep |
Almost Optimal Inapproximability of Multidimensional Packing Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR21, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee |
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR21, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Naoto Ohsaka |
Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2109.00727, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Karthik C. S., Subhash Khot |
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2112.03983, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Erika Melder |
A Chronology of Set Cover Inapproximability Results. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2111.08100, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Jamie Tucker-Foltz |
Inapproximability of Unique Games in Fixed-Point Logic with Counting. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2104.04566, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Xuandi Ren |
A Survey on Parameterized Inapproximability: k-Clique, k-SetCover, and More. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2112.04669, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Hengzhao Ma, Jianzhong Li 0001 |
The PCP-like Theorem for Sub-linear Time Inapproximability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2107.01520, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Ulrich Bauer, Abhishek Rathod |
Parameterized inapproximability of Morse matching. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2109.04529, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Sai Sandeep |
Almost Optimal Inapproximability of Multidimensional Packing Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2101.02854, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee |
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2111.10912, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Alex Meiburg |
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2111.03142, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | David Stein, Bjoern Andres |
Inapproximability of Minimizing a Pair of DNFs or Binary Decision Trees Defining a Partial Boolean Function. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2102.04703, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Andreas Galanis, Heng Guo 0001, Jiaheng Wang 0002 |
Inapproximability of counting hypergraph colourings. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2107.05486, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Per Austrin, Jonah Brown-Cohen, Johan Håstad |
Optimal Inapproximability with Universal Factor Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pp. 434-453, 2021, SIAM, 978-1-61197-646-5. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Jamie Tucker-Foltz |
Inapproximability of Unique Games in Fixed-Point Logic with Counting. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LICS ![In: 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pp. 1-13, 2021, IEEE, 978-1-6654-4895-6. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Sai Sandeep |
Almost Optimal Inapproximability of Multidimensional Packing Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pp. 245-256, 2021, IEEE, 978-1-6654-2055-6. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Marcelo Pinheiro Leite Benedito, Lehilton L. C. Pedrosa, Hugo K. K. Rosado |
On the Inapproximability of the Cable-Trench Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LAGOS ![In: Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2021, Online Event / São Paulo, Brazil, May 2021., pp. 39-48, 2021, Elsevier. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Édouard Bonnet |
Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference)., pp. 17:1-17:13, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-180-1. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski |
Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WAOA ![In: Approximation and Online Algorithms - 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6-10, 2021, Revised Selected Papers, pp. 48-64, 2021, Springer, 978-3-030-92701-1. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Amey Bhangale, Subhash Khot |
Optimal inapproximability of satisfiable k-LIN over non-abelian groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021., pp. 1615-1628, 2021, ACM, 978-1-4503-8053-9. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
18 | Naoto Ohsaka |
Unconstrained MAP Inference, Exponentiated Determinantal Point Processes, and Exponential Inapproximability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
AISTATS ![In: The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event., pp. 154-162, 2021, PMLR. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
18 | Matthias Rost, Stefan Schmid 0001 |
On the Hardness and Inapproximability of Virtual Network Embeddings. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IEEE/ACM Trans. Netw. ![In: IEEE/ACM Trans. Netw. 28(2), pp. 791-803, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Amey Bhangale, Subhash Khot |
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR20, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | Sören Henning, Klaus Jansen, Malin Rau, Lars Schmarje |
Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 64(1), pp. 120-140, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Édouard Bonnet |
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2008.11315, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | Amey Bhangale, Subhash Khot |
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2009.02815, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | Pavel Dvorák, Andreas Emil Feldmann, Ashutosh Rai 0001, Pawel Rzazewski |
Parameterized Inapproximability of Independent Set in H-Free Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2006.10444, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum, Matthias Mnich |
Dense Steiner problems: Approximation algorithms and inapproximability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2004.14102, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | |
PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2011.02320, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | Yuval Efron, Ofer Grossman, Seri Khoury |
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2003.07427, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee |
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2010.01459, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
18 | Jason M. Altschuler, Pablo A. Parrilo |
Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Control. Optim. ![In: SIAM J. Control. Optim. 58(1), pp. 510-528, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Yixin Cao 0001, R. B. Sandeep |
Minimum fill-in: Inapproximability and almost tight lower bounds. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Comput. ![In: Inf. Comput. 271, pp. 104514, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan |
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 49(4), pp. 772-810, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic |
Inapproximability of the Independent Set Polynomial in the Complex Plane. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 49(5), 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | 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). ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020., pp. 62-81, 2020, SIAM, 978-1-61197-599-4. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Per Austrin, Amey Bhangale, Aditya Potukuchi |
Improved Inapproximability of Rainbow Coloring. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020., pp. 1479-1495, 2020, SIAM, 978-1-61197-599-4. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Michal Wlodarczyk 0001 |
Parameterized Inapproximability for Steiner Orientation by Gap Amplification. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)., pp. 104:1-104:19, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-138-2. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Pavel Dvorák, Andreas Emil Feldmann, Ashutosh Rai 0001, Pawel Rzazewski |
Parameterized Inapproximability of Independent Set in H-Free Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WG ![In: Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers, pp. 40-53, 2020, Springer, 978-3-030-60439-4. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Yuval Efron, Ofer Grossman, Seri Khoury |
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST. ![Search on Bibsonomy](Pics/bibsonomy.png) |
PODC ![In: PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pp. 511-520, 2020, ACM, 978-1-4503-7582-5. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Marten Maack, Klaus Jansen |
Inapproximability Results for Scheduling with Interval and Resource Restrictions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France., pp. 5:1-5:18, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-140-5. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
18 | Alex Olshevsky |
On the Inapproximability of the Discrete Witsenhausen Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IEEE Control. Syst. Lett. ![In: IEEE Control. Syst. Lett. 3(3), pp. 529-534, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Pasin Manurangsi |
A note on degree vs gap of Min-Rep Label Cover and improved inapproximability for connectivity problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 145, pp. 24-29, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Xiaojun Zhu 0001, Bing Chen 0002, Muhui Shen, Yanchao Zhao |
Inapproximability results and suboptimal algorithms for minimum delay cache placement in campus networks with content-centric network routers. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Supercomput. ![In: J. Supercomput. 75(8), pp. 5451-5474, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Per Austrin, Jonah Brown-Cohen, Johan Håstad |
Optimal Inapproximability with Universal Factor Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR19, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | Alex Olshevsky |
On the Inapproximability of the Discrete Witsenhausen Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1904.05701, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | 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). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1910.11850, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | Siddhartha Jain 0002 |
Inapproximability of Additive Weak Contraction under SSEH and Strong UGC. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1912.00143, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | Rajesh Chitnis, Andreas Emil Feldmann |
FPT Inapproximability of Directed Cut and Connectivity Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1910.01934, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | Daniel Gibney, Sharma V. Thankachan |
On the Hardness and Inapproximability of Recognizing Wheeler Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1902.01960, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | |
Parameterized Inapproximability of Exact Cover and Nearest Codeword. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1905.06503, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | Michal Wlodarczyk 0001 |
Inapproximability within W[1]: the case of Steiner Orientation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1907.06529, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | Marten Maack, Klaus Jansen |
Inapproximability Results for Scheduling with Interval and Resource Restrictions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1907.03526, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
18 | Albert Atserias, Anuj Dawar |
Definable inapproximability: new challenges for duplicator. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Log. Comput. ![In: J. Log. Comput. 29(8), pp. 1185-1210, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Wenxing Lai |
The Inapproximability of k-DominatingSet for Parameterized AC 0 Circuits †. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithms ![In: Algorithms 12(11), pp. 230, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Yijia Chen, Bingkai Lin |
The Constant Inapproximability of the Parameterized Dominating Set Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 48(2), pp. 513-533, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Vincent Cohen-Addad, Karthik C. S. |
Inapproximability of Clustering in Lp Metrics. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pp. 519-539, 2019, IEEE Computer Society, 978-1-7281-4952-3. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Daniel Gibney, Sharma V. Thankachan |
On the Hardness and Inapproximability of Recognizing Wheeler Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ESA ![In: 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany., pp. 51:1-51:16, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-124-5. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Jason M. Altschuler, Pablo A. Parrilo |
Lyapunov Exponent of Rank One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CDC ![In: 58th IEEE Conference on Decision and Control, CDC 2019, Nice, France, December 11-13, 2019, pp. 4439-4445, 2019, IEEE, 978-1-7281-1398-2. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Wenxing Lai |
The Inapproximability of k-DominatingSet for Parameterized \mathsf AC^0 AC 0 Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FAW ![In: Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Sanya, China, April 29 - May 3, 2019, Proceedings, pp. 133-143, 2019, Springer, 978-3-030-18125-3. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Yousef M. Alhamdan, Alexander V. Kononov |
Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSR ![In: Computer Science - Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1-5, 2019, Proceedings, pp. 1-12, 2019, Springer, 978-3-030-19954-8. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Rajesh Chitnis, Andreas Emil Feldmann |
FPT Inapproximability of Directed Cut and Connectivity Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IPEC ![In: 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany., pp. 8:1-8:20, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-129-0. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
18 | Venkatesan Guruswami, Euiwoong Lee |
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Comb. ![In: Comb. 38(3), pp. 547-599, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Kaourintin Le Guiban, Arpad Rimmel, Marc-Antoine Weisser, Joanna Tomasik |
Completion of partial Latin Hypercube Designs: NP-completeness and inapproximability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 715, pp. 1-20, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee, Bang Ye Wu |
Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comput. Syst. Sci. ![In: J. Comput. Syst. Sci. 92, pp. 92-112, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
Inapproximability of Matrix p→q Norms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR18, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
18 | Suman Banerjee 0002, Rogers Mathew |
An Inapproximability Result for the Target Set Selection Problem on Bipartite Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1812.01482, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
18 | Pasin Manurangsi |
A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1807.00936, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
18 | Albert Atserias, Anuj Dawar |
Definable Inapproximability: New Challenges for Duplicator. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1806.11307, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
18 | Matthias Rost, Stefan Schmid 0001 |
NP-Completeness and Inapproximability of the Virtual Network Embedding Problem and Its Variants. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1801.03162, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
18 | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
Inapproximability of Matrix p→q Norms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1802.07425, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
18 | Per Austrin, Amey Bhangale, Aditya Potukuchi |
Improved Inapproximability of Rainbow Coloring. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1810.02784, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
18 | Pasin Manurangsi |
Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithms ![In: Algorithms 11(1), pp. 10, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Koichi Yamazaki |
Inapproximability of Rank, Clique, Boolean, and Maximum Induced Matching-Widths under Small Set Expansion Hypothesis. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithms ![In: Algorithms 11(11), pp. 173, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Argyrios Deligkas, John Fearnley, Rahul Savani |
Inapproximability results for constrained approximate Nash equilibria. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Comput. ![In: Inf. Comput. 262, pp. 40-56, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Sonia Toubaline, Claudia D'Ambrosio, Leo Liberti, Pierre-Louis Poirion, Baruch Schieber, Hadas Shachnai |
Complexity and inapproximability results for the Power Edge Set problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comb. Optim. ![In: J. Comb. Optim. 35(3), pp. 895-905, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Aviad Rubinstein |
Inapproximability of Nash Equilibrium. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 47(3), pp. 917-959, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Amit Daniely, Michael Schapira, Gal Shahaf |
Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik-Chervonenkis Dimension. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 47(1), pp. 96-120, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Sören Henning, Klaus Jansen, Malin Rau, Lars Schmarje |
Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSR ![In: Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings, pp. 169-180, 2018, Springer, 978-3-319-90529-7. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic |
Inapproximability of the independent set polynomial in the complex plane. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 1234-1240, 2018, ACM. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Albert Atserias, Anuj Dawar |
Definable Inapproximability: New Challenges for Duplicator. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: 27th EACSL Annual Conference on Computer Science Logic, CSL 2018, September 4-7, 2018, Birmingham, UK, pp. 7:1-7:21, 2018, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-088-0. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
18 | Rafael Veiga Pocai |
Inapproximability Ratios for Crossing Number. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Notes Discret. Math. ![In: Electron. Notes Discret. Math. 62, pp. 117-122, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
18 | Euiwoong Lee, Melanie Schmidt 0001, John Wright 0004 |
Improved and simplified inapproximability for k-means. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 120, pp. 40-43, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
18 | Malik Magdon-Ismail |
NP-hardness and inapproximability of sparse PCA. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 126, pp. 35-38, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
18 | F. Bruce Shepherd, Adrian R. Vetta |
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. ![In: Theory Comput. 13(1), pp. 1-25, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
18 | Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright 0004 |
Improved NP-Inapproximability for 2-Variable Linear Equations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. ![In: Theory Comput. 13(1), pp. 1-51, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
18 | Venkatesan Guruswami, Euiwoong Lee |
Inapproximability of H-Transversal/Packing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Discret. Math. ![In: SIAM J. Discret. Math. 31(3), pp. 1552-1571, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
18 | Joshua Brakensiek, Venkatesan Guruswami |
The Quest for Strong Inapproximability Results with Perfect Completeness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR17, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
18 | Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan |
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1708.04218, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|