Quasi-Random PCP and Hardness of 2-Catalog Segmentation

DOI10.4230/LIPIcs.FSTTCS.2010.447zbMath1245.68095OpenAlexW2167194753MaRDI QIDQ2908876

Rishi Saket

Publication date: 29 August 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_3442.html

zbMATH Keywords

hardness of approximationcatalog segmentationPCPs

Mathematics Subject Classification ID

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

Related Items (2)

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems

This page was built for publication: Quasi-Random PCP and Hardness of 2-Catalog Segmentation