scientific article
From MaRDI portal
Publication:3002828
DOI10.4086/toc.2011.v007a003zbMath1243.68183OpenAlexW1491127810MaRDI QIDQ3002828
Per Austrin, Shmuel Safra, Subhash A. Khot
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2011.v007a003
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (34)
Independent sets in semi-random hypergraphs ⋮ Complexity of approximating CSP with balance/hard constraints ⋮ Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014. ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ Secluded connectivity problems ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Inductive graph invariants and approximation algorithms ⋮ On the parameterized complexity of compact set packing ⋮ Competitive and collaborative influence in social networks ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Locally Stable Marriage with Strict Preferences ⋮ Donation center location problem ⋮ Maximum Weighted Independent Sets with a Budget ⋮ New techniques for approximating optimal substructure problems in power-law graphs ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ Complexity and lowers bounds for power edge set problem ⋮ Affine reductions for LPs and SDPs ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Recoverable Values for Independent Sets ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Unnamed Item ⋮ On Constant Time Approximation of Parameters of Bounded Degree Graphs ⋮ Approximation in (Poly-) logarithmic space ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Multitasking Capacity: Hardness Results and Improved Constructions ⋮ Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs ⋮ Approximation in (Poly-) Logarithmic Space ⋮ UG-hardness to NP-hardness by losing half ⋮ Simultaneous max-cut is harder to approximate than max-cut ⋮ Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses ⋮ Approximation algorithms for vertex happiness ⋮ Unnamed Item
This page was built for publication:
