Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant

DOI10.1137/090756144zbMath1235.68075OpenAlexW2056590617WikidataQ56958820 ScholiaQ56958820MaRDI QIDQ3093627

Prasad Raghavendra, Rajsekar Manokaran, Moses Charikar, Venkatesan Guruswami, Johan T. Håstad

Publication date: 18 October 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ec414204729bc4c1cc3edbc7e1f70eb06543cf4f

zbMATH Keywords

hardness of approximationfeedback arc setunique games conjectureintegrality gapsmaximum acyclic subgraph

Mathematics Subject Classification ID

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

Related Items (23)

Improved Parameterized Algorithms for above Average Constraint Satisfaction ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Testing Consumer Rationality Using Perfect Graphs and Oriented Discs ⋮ Parameterized complexity of MaxSat above average ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Unnamed Item ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees ⋮ Unnamed Item ⋮ A priori TSP in the Scenario Model ⋮ Approximation Algorithms for CSPs ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ Target set selection for conservative populations ⋮ Maximizing Polynomials Subject to Assignment Constraints ⋮ A priori TSP in the scenario model ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ Approximating the Maximum Rectilinear Crossing Number ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems ⋮ Simultaneous max-cut is harder to approximate than max-cut ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Unnamed Item ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction

This page was built for publication: Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant