Name
Abstract | ||
|---|---|---|
Let A be a 0 − 1 matrix with precisely two 1’s in each column and let 1 be the all-one vector. We show that the problems of deciding whether the linear system $${A{\bf x} \ge {\bf 1}, {\bf x}\ge {\bf 0}}$$ (1) defines an integral polyhedron, (2) is totally dual integral (TDI), and (3) box-totally dual integral (box-TDI) are all co-NP-complete, thereby confirming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles in 1984. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10107-007-0103-y | Math. Program. |
Keywords | Field | DocType |
linear system · polyhedron · total dual integrality · np-hardness,all-one vector,linear system,certain integrality property,integral polyhedron,tdi system,polyhedron | Discrete mathematics,Combinatorics,NP-complete,Linear system,Matrix (mathematics),Polyhedron,Total dual integrality,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
114 | 2 | 1436-4646 |
Citations | PageRank | References |
17 | 1.30 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoli Ding | 1 | 444 | 51.58 |
| Li Feng | 2 | 17 | 1.30 |
| Wenan Zang | 3 | 305 | 39.19 |