User: Guest  Login
Document type:
Buchbeitrag 
Author(s):
Brieden, A. and P. Gritzmann 
Title:
On the inapproximability of polynomial-programming, the geometry of stable sets and the power of relaxation 
Pages contribution:
303-313 
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. As a consequence we obtain very ti...    »
 
Editor:
B. Aronov et al. 
Book title:
Discrete and Computational Geometry 
Book subtitle:
The Goodman-Pollack Festschrift 
Publisher:
Springer 
Publisher address:
New York 
Year:
2003 
Reviewed:
ja 
Language:
en 
TUM Institution:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik 
Format:
Text