共 1 条
- [1] The negative cycles polyhedron and hardness of checking some polyhedral propertiesAnnals of Operations Research, 2011, 188 : 63 - 76Endre BorosKhaled ElbassioniVladimir GurvichHans Raj Tiwary
The negative cycles polyhedron and hardness of checking some polyhedral properties
被引：6
|作者：
Boros, Endre
[2
]
Elbassioni, Khaled
[1
]
Gurvich, Vladimir
[2
]
Tiwary, Hans Raj
[3
]
机构：
[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany
[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
[3] Tech Univ Berlin, Inst Math, Fak 2, D-10623 Berlin, Germany
基金：
美国国家科学基金会;
关键词：
Flow polytope;
0/1-polyhedron;
Vertex;
Extreme direction;
Enumeration problem;
Negative cycles;
Directed graph;
Half-integral polyhedra;
Maximum support;
Hardness of approximation;
VERTICES;
VERTEX;
ENUMERATION;
COMPLEXITY;
CUTS;
D O I：
10.1007/s10479-010-0690-5
中图分类号：
C93 [管理学];
O22 [运筹学];
学科分类号：
070105 ;
12 ;
1201 ;
1202 ;
120202 ;
摘要：
Given a graph G=(V,E) and a weight function on the edges w:E -> a"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. (Discrete Comput. Geom. 39(1-3):174-190, 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. (Discrete Comput. Geom. 39(1-3):174-190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lubbecke in Comput. Geom., Theory Appl. 11(2):103-109, 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 a"e (n) within a factor of 12/n.
引用
收藏
页码：63 / 76
页数：14
相关论文