| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 18 | Jean Cardinal, Raphael Steiner |
Inapproximability of shortest paths on perfect matching polytopes.  |
CoRR  |
2022 |
DBLP DOI BibTeX RDF |
|
| 18 | Andreas Galanis, Heng Guo 0001, Jiaheng Wang 0002 |
Inapproximability of Counting Hypergraph Colourings. |
ACM Trans. Comput. Theory |
2022 |
DBLP DOI BibTeX RDF |
|
| 18 | Miroslav Chlebík, Janka Chlebíková |
Weighted amplifiers and inapproximability results for Travelling Salesman problem. |
J. Comb. Optim. |
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. |
SODA |
2022 |
DBLP DOI BibTeX RDF |
|
| 18 | Alexander Meiburg |
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 18 | Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos |
Pure-Circuit: Strong Inapproximability for PPAD. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 18 | Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos |
Constant inapproximability for PPA. |
STOC |
2022 |
DBLP DOI BibTeX RDF |
|
| 18 | Karthik C. S., Subhash Khot |
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 18 | Joshua Brakensiek, Venkatesan Guruswami |
The Quest for Strong Inapproximability Results with Perfect Completeness. |
ACM Trans. Algorithms |
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. |
Theor. Comput. Sci. |
2021 |
DBLP DOI BibTeX RDF |
|
| 18 | Sai Sandeep |
Almost Optimal Inapproximability of Multidimensional Packing Problems. |
Electron. Colloquium Comput. Complex. |
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. |
Electron. Colloquium Comput. Complex. |
2021 |
DBLP BibTeX RDF |
|
| 18 | Naoto Ohsaka |
Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Karthik C. S., Subhash Khot |
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Erika Melder |
A Chronology of Set Cover Inapproximability Results. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Jamie Tucker-Foltz |
Inapproximability of Unique Games in Fixed-Point Logic with Counting. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Xuandi Ren |
A Survey on Parameterized Inapproximability: k-Clique, k-SetCover, and More. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Hengzhao Ma, Jianzhong Li 0001 |
The PCP-like Theorem for Sub-linear Time Inapproximability. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Ulrich Bauer, Abhishek Rathod |
Parameterized inapproximability of Morse matching. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Sai Sandeep |
Almost Optimal Inapproximability of Multidimensional Packing Problems. |
CoRR |
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. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Alex Meiburg |
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography. |
CoRR |
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. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Andreas Galanis, Heng Guo 0001, Jiaheng Wang 0002 |
Inapproximability of counting hypergraph colourings. |
CoRR |
2021 |
DBLP BibTeX RDF |
|
| 18 | Per Austrin, Jonah Brown-Cohen, Johan Håstad |
Optimal Inapproximability with Universal Factor Graphs. |
SODA |
2021 |
DBLP DOI BibTeX RDF |
|
| 18 | Jamie Tucker-Foltz |
Inapproximability of Unique Games in Fixed-Point Logic with Counting. |
LICS |
2021 |
DBLP DOI BibTeX RDF |
|
| 18 | Sai Sandeep |
Almost Optimal Inapproximability of Multidimensional Packing Problems. |
FOCS |
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. |
LAGOS |
2021 |
DBLP DOI BibTeX RDF |
|
| 18 | Édouard Bonnet |
Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio. |
STACS |
2021 |
DBLP DOI BibTeX RDF |
|
| 18 | Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski |
Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems. |
WAOA |
2021 |
DBLP DOI BibTeX RDF |
|
| 18 | Amey Bhangale, Subhash Khot |
Optimal inapproximability of satisfiable k-LIN over non-abelian groups. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 18 | Naoto Ohsaka |
Unconstrained MAP Inference, Exponentiated Determinantal Point Processes, and Exponential Inapproximability. |
AISTATS |
2021 |
DBLP BibTeX RDF |
|
| 18 | Matthias Rost, Stefan Schmid 0001 |
On the Hardness and Inapproximability of Virtual Network Embeddings. |
IEEE/ACM Trans. Netw. |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Amey Bhangale, Subhash Khot |
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. |
Electron. Colloquium Comput. Complex. |
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. |
Theory Comput. Syst. |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Édouard Bonnet |
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio. |
CoRR |
2020 |
DBLP BibTeX RDF |
|
| 18 | Amey Bhangale, Subhash Khot |
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. |
CoRR |
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. |
CoRR |
2020 |
DBLP BibTeX RDF |
|
| 18 | Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum, Matthias Mnich |
Dense Steiner problems: Approximation algorithms and inapproximability. |
CoRR |
2020 |
DBLP BibTeX RDF |
|
| 18 | |
PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability. |
CoRR |
2020 |
DBLP BibTeX RDF |
|
| 18 | Yuval Efron, Ofer Grossman, Seri Khoury |
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST. |
CoRR |
2020 |
DBLP BibTeX RDF |
|
| 18 | Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee |
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering. |
CoRR |
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. |
SIAM J. Control. Optim. |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Yixin Cao 0001, R. B. Sandeep |
Minimum fill-in: Inapproximability and almost tight lower bounds. |
Inf. Comput. |
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. |
SIAM J. Comput. |
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. |
SIAM J. Comput. |
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). |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Per Austrin, Amey Bhangale, Aditya Potukuchi |
Improved Inapproximability of Rainbow Coloring. |
SODA |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Michal Wlodarczyk 0001 |
Parameterized Inapproximability for Steiner Orientation by Gap Amplification. |
ICALP |
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. |
WG |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Yuval Efron, Ofer Grossman, Seri Khoury |
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST. |
PODC |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Marten Maack, Klaus Jansen |
Inapproximability Results for Scheduling with Interval and Resource Restrictions. |
STACS |
2020 |
DBLP DOI BibTeX RDF |
|
| 18 | Alex Olshevsky |
On the Inapproximability of the Discrete Witsenhausen Problem. |
IEEE Control. Syst. Lett. |
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. |
Inf. Process. Lett. |
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. |
J. Supercomput. |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Per Austrin, Jonah Brown-Cohen, Johan Håstad |
Optimal Inapproximability with Universal Factor Graphs. |
Electron. Colloquium Comput. Complex. |
2019 |
DBLP BibTeX RDF |
|
| 18 | Alex Olshevsky |
On the Inapproximability of the Discrete Witsenhausen Problem. |
CoRR |
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). |
CoRR |
2019 |
DBLP BibTeX RDF |
|
| 18 | Siddhartha Jain 0002 |
Inapproximability of Additive Weak Contraction under SSEH and Strong UGC. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
| 18 | Rajesh Chitnis, Andreas Emil Feldmann |
FPT Inapproximability of Directed Cut and Connectivity Problems. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
| 18 | Daniel Gibney, Sharma V. Thankachan |
On the Hardness and Inapproximability of Recognizing Wheeler Graphs. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
| 18 | |
Parameterized Inapproximability of Exact Cover and Nearest Codeword. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
| 18 | Michal Wlodarczyk 0001 |
Inapproximability within W[1]: the case of Steiner Orientation. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
| 18 | Marten Maack, Klaus Jansen |
Inapproximability Results for Scheduling with Interval and Resource Restrictions. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
| 18 | Albert Atserias, Anuj Dawar |
Definable inapproximability: new challenges for duplicator. |
J. Log. Comput. |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Wenxing Lai |
The Inapproximability of k-DominatingSet for Parameterized AC 0 Circuits †. |
Algorithms |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Yijia Chen, Bingkai Lin |
The Constant Inapproximability of the Parameterized Dominating Set Problem. |
SIAM J. Comput. |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Vincent Cohen-Addad, Karthik C. S. |
Inapproximability of Clustering in Lp Metrics. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Daniel Gibney, Sharma V. Thankachan |
On the Hardness and Inapproximability of Recognizing Wheeler Graphs. |
ESA |
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. |
CDC |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Wenxing Lai |
The Inapproximability of k-DominatingSet for Parameterized \mathsf AC^0 AC 0 Circuits. |
FAW |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Yousef M. Alhamdan, Alexander V. Kononov |
Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem. |
CSR |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Rajesh Chitnis, Andreas Emil Feldmann |
FPT Inapproximability of Directed Cut and Connectivity Problems. |
IPEC |
2019 |
DBLP DOI BibTeX RDF |
|
| 18 | Venkatesan Guruswami, Euiwoong Lee |
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. |
Comb. |
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. |
Theor. Comput. Sci. |
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. |
J. Comput. Syst. Sci. |
2018 |
DBLP DOI BibTeX RDF |
|
| 18 | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
Inapproximability of Matrix p→q Norms. |
Electron. Colloquium Comput. Complex. |
2018 |
DBLP BibTeX RDF |
|
| 18 | Suman Banerjee 0002, Rogers Mathew |
An Inapproximability Result for the Target Set Selection Problem on Bipartite Graphs. |
CoRR |
2018 |
DBLP BibTeX RDF |
|
| 18 | Pasin Manurangsi |
A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems. |
CoRR |
2018 |
DBLP BibTeX RDF |
|
| 18 | Albert Atserias, Anuj Dawar |
Definable Inapproximability: New Challenges for Duplicator. |
CoRR |
2018 |
DBLP BibTeX RDF |
|
| 18 | Matthias Rost, Stefan Schmid 0001 |
NP-Completeness and Inapproximability of the Virtual Network Embedding Problem and Its Variants. |
CoRR |
2018 |
DBLP BibTeX RDF |
|
| 18 | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
Inapproximability of Matrix p→q Norms. |
CoRR |
2018 |
DBLP BibTeX RDF |
|
| 18 | Per Austrin, Amey Bhangale, Aditya Potukuchi |
Improved Inapproximability of Rainbow Coloring. |
CoRR |
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. |
Algorithms |
2018 |
DBLP DOI BibTeX RDF |
|
| 18 | Koichi Yamazaki |
Inapproximability of Rank, Clique, Boolean, and Maximum Induced Matching-Widths under Small Set Expansion Hypothesis. |
Algorithms |
2018 |
DBLP DOI BibTeX RDF |
|
| 18 | Argyrios Deligkas, John Fearnley, Rahul Savani |
Inapproximability results for constrained approximate Nash equilibria. |
Inf. Comput. |
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. |
J. Comb. Optim. |
2018 |
DBLP DOI BibTeX RDF |
|
| 18 | Aviad Rubinstein |
Inapproximability of Nash Equilibrium. |
SIAM J. Comput. |
2018 |
DBLP DOI BibTeX RDF |
|
| 18 | Amit Daniely, Michael Schapira, Gal Shahaf |
Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik-Chervonenkis Dimension. |
SIAM J. Comput. |
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. |
CSR |
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. |
STOC |
2018 |
DBLP DOI BibTeX RDF |
|
| 18 | Albert Atserias, Anuj Dawar |
Definable Inapproximability: New Challenges for Duplicator. |
CSL |
2018 |
DBLP DOI BibTeX RDF |
|
| 18 | Rafael Veiga Pocai |
Inapproximability Ratios for Crossing Number. |
Electron. Notes Discret. Math. |
2017 |
DBLP DOI BibTeX RDF |
|
| 18 | Euiwoong Lee, Melanie Schmidt 0001, John Wright 0004 |
Improved and simplified inapproximability for k-means. |
Inf. Process. Lett. |
2017 |
DBLP DOI BibTeX RDF |
|
| 18 | Malik Magdon-Ismail |
NP-hardness and inapproximability of sparse PCA. |
Inf. Process. Lett. |
2017 |
DBLP DOI BibTeX RDF |
|
| 18 | F. Bruce Shepherd, Adrian R. Vetta |
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems. |
Theory Comput. |
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. |
Theory Comput. |
2017 |
DBLP DOI BibTeX RDF |
|
| 18 | Venkatesan Guruswami, Euiwoong Lee |
Inapproximability of H-Transversal/Packing. |
SIAM J. Discret. Math. |
2017 |
DBLP DOI BibTeX RDF |
|
| 18 | Joshua Brakensiek, Venkatesan Guruswami |
The Quest for Strong Inapproximability Results with Perfect Completeness. |
Electron. Colloquium Comput. Complex. |
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. |
CoRR |
2017 |
DBLP BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license