Retour

G-2003-05

On the Complexity of Testing Hypermetric, Negative Type, k-gonal and Gap Inequalities

référence BibTeX

Hypermetric inequalities have many applications, most recently in the approximate solution of max-cut problems by linear and semidefinite programming. However not much is known about the separation problem for these inequalities. Previously Avis and Grishukhin showed that certain special cases of the separation problem for hypermetric inequalities are NP-hard, as evidence that the separation problem is itself hard. In this paper we show that similar results hold for inequalities of negative type, even though the separation problem for negative type inequalities is well known to be solvable in polynomial time. We also show similar results hold for the more general k-gonal and gap inequalities.

, 12 pages

Publication

On the Complexity of Testing Hypermetric, Negative Type, k-gonal and Gap Inequalities
Discrete and Computational Geometry, Lecture Notes in Computer Science, 2866, 51–59, 2003 référence BibTeX