The negative cycles polyhedron and hardness of checking some polyhedral properties

The negative cycles polyhedron and hardness of checking some polyhedral properties

0.00 Avg rating0 Votes
Article ID: iaor20117920
Volume: 188
Issue: 1
Start Page Number: 63
End Page Number: 76
Publication Date: Aug 2011
Journal: Annals of Operations Research
Authors: , , ,
Abstract:

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative‐weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (2008), we show that, unless P=NP, there is no output polynomial‐time algorithm to generate all the vertices of a 0/1‐polyhedron. This strengthens the NP‐hardness result of Khachiyan et al. (2008) for non 0/1‐polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1‐polytopes (1998). As further applications, we show that it is NP‐hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half‐integral. Finally, we also show that it is NP‐hard to approximate the maximum support of a vertex of a polyhedron in ℝ n within a factor of 12/n.

Reviews

Required fields are marked *. Your email address will not be published.