Login
Document type:
Sammelbandbeitrag / Paper in Collective Volume
Title:
On the inapproximability of polynomial programming, the geometry of stable sets, and the power of relaxation
Collection title:
Discrete and Computational Geometry
Collection subtitle:
The Goodman-Pollack Festschrift
Collection editors:
Aronov, Boris; Basu, Saugata; Pach, Janos; Sharir, Micha
Series title:
Discrete and Computational Geometry. Algorithms and Combinatorics
Series volume:
25
Place of publication:
Berlin ; Heidelberg
Publisher:
Springer
Year:
2003
Pages from - to:
301-311
Language:
Englisch
Abstract:
The present paper introduces the geometric rank as a measure for the quality of relaxations of certain combinatorial optimization problems in the realm of polyhedral combinatorics. In particular, this notion establishes a tight relation between the maximum stable set problem from combinatorial optimization, polynomial programming from integer non linear programming and norm maximization, a basic problem from convex maximization and computational convexity.
ISBN:
978-3-642-62442-1
Department:
Fakultät für Wirtschafts- und Organisationswissenschaften
Institute:
WOW 1 - Institut für Controlling, Finanz- und Risikomanagement
Chair:
Brieden, Andreas
Open Access yes or no?:
Nein / No
BibTeX