scientific article; zbMATH DE number 7204530
From MaRDI portal
Publication:5111409
DOI10.4230/LIPIcs.ICALP.2017.78zbMath1441.68048arXiv1607.02986MaRDI QIDQ5111409
Prasad Raghavendra, Pasin Manurangsi
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1607.02986
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)
Related Items (25)
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Improved parameterized approximation for balanced \(k\)-median ⋮ A note on the concrete hardness of the shortest independent vector in lattices ⋮ Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation ⋮ Integrality gaps for colorful matchings ⋮ Lower tails via relative entropy ⋮ Complexity of minimum-size arc-inconsistency explanations ⋮ Approximation schemes for \(k\)-facility location ⋮ Unnamed Item ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Approximation and hardness of shift-Bribery ⋮ A tight lower bound for planar Steiner orientation ⋮ Lossy kernelization of same-size clustering ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ Short Proofs Are Hard to Find ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Lossy kernelization of same-size clustering ⋮ On parameterized approximation algorithms for balanced clustering ⋮ To close is easier than to open: dual parameterization to \(k\)-median
This page was built for publication:
