Optimal Long Code Test with One Free Bit

DOI10.1109/FOCS.2009.23zbMath1292.68081OpenAlexW2152490496MaRDI QIDQ5171195

Subhash A. Khot, Nikhil Bansal

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.23

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (24)

Towards Tight Lower Bounds for Scheduling Problems ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ On Submodular Search and Machine Scheduling ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Unnamed Item ⋮ Timeline cover in temporal graphs: exact and approximation algorithms ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ Scheduling results applicable to decision-theoretic troubleshooting ⋮ Approximating Weighted Completion Time for Order Scheduling with Setup Times ⋮ Quasi-PTAS for scheduling with precedences using LP hierarchies ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Preemptive and non-preemptive generalized min sum set cover ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Strong reductions for extended formulations ⋮ Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Makespan minimization with OR-precedence constraints ⋮ An improved approximation algorithm for scheduling under arborescence precedence constraints ⋮ A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness

This page was built for publication: Optimal Long Code Test with One Free Bit