ECCC - TR03-008

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR03-008 | 11th February 2003 00:00

Improved Approximation Lower Bounds on Small Occurrence Optimization

Contact

Add Comment

TR03-008 Authors: Piotr Berman, Marek Karpinski
Publication: 11th February 2003 10:04
Downloads: 4345

Keywords:

Approximation Algorithms, Approximation Hardness, Bounded Occurrence Instances, Gap Property, Linear Equations, lower bounds, MAX-SAT, Maximum Independent Set, Maximum 3D-Matching, Regular Amplifiers

Abstract:

We improve a number of approximation lower bounds for
bounded occurrence optimization problems like MAX-2SAT,
E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching.

ISSN 1433-8092 | Imprint