Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6861
Title: Quantifiers and Approximation
Authors: Panconesi, Alessandro
Ranjan, Desh
Keywords: computer science
technical report
Issue Date: Nov-1989
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1061
Abstract: We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitriou and Yannakakis, who defined the class of NPO problems MAX NP. We show that many important optimization problems do not belong to MAX NP and that in fact there are problems in P which are not is MAXNP. The problems we consider fit naturally in a new complexity class that we call MAX II sub 1. We prove that several natural optimization problems are complete for MAX II sub 1 under approximation preserving reductions. All these complete problems are non-approximable unless P=NP. This motivates the definition of subclasses of MAX II sub 1 that only contain problems which are presumably easier with respect to approximation. In particular, the class that we call RMAX(2), contains approximable problems and problems like MAX CLIQUE that are not known to be non-approximable. We prove that MAX CLIQUE and other natural optimization problems are complete for RMAX(2). All the complete problems in RMAX(2) share the interesting property that they either are non-approximable or are approximable to any degree of accuracy.
URI: http://hdl.handle.net/1813/6861
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
89-1061.pdf1.65 MBAdobe PDFView/Open
89-1061.ps355.35 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us