File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10107-007-0103-y
- Scopus: eid_2-s2.0-42149163701
- WOS: WOS:000254805300006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: The complexity of recognizing linear systems with certain integrality properties
Title | The complexity of recognizing linear systems with certain integrality properties |
---|---|
Authors | |
Keywords | Linear system NP-hardness Polyhedron Total dual integrality |
Issue Date | 2008 |
Publisher | Springer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/10107/ |
Citation | Mathematical Programming, 2008, v. 114 n. 2, p. 321-334 How to Cite? |
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 Ax ≥ 1,x ≥ 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. © 2007 Springer-Verlag. |
Persistent Identifier | http://hdl.handle.net/10722/58972 |
ISSN | 2023 Impact Factor: 2.2 2023 SCImago Journal Rankings: 1.982 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ding, G | en_HK |
dc.contributor.author | Feng, L | en_HK |
dc.contributor.author | Zang, W | en_HK |
dc.date.accessioned | 2010-05-31T03:40:36Z | - |
dc.date.available | 2010-05-31T03:40:36Z | - |
dc.date.issued | 2008 | en_HK |
dc.identifier.citation | Mathematical Programming, 2008, v. 114 n. 2, p. 321-334 | en_HK |
dc.identifier.issn | 0025-5610 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/58972 | - |
dc.description.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 Ax ≥ 1,x ≥ 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. © 2007 Springer-Verlag. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/10107/ | en_HK |
dc.relation.ispartof | Mathematical Programming | en_HK |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.subject | Linear system | en_HK |
dc.subject | NP-hardness | en_HK |
dc.subject | Polyhedron | en_HK |
dc.subject | Total dual integrality | en_HK |
dc.title | The complexity of recognizing linear systems with certain integrality properties | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0025-5610&volume=114&spage=321&epage=334&date=2008&atitle=The+Complexity+Of+Recognizing+Linear+Systems+With+Certain+Integrality+Properties | en_HK |
dc.identifier.email | Zang, W:wzang@maths.hku.hk | en_HK |
dc.identifier.authority | Zang, W=rp00839 | en_HK |
dc.description.nature | preprint | - |
dc.identifier.doi | 10.1007/s10107-007-0103-y | en_HK |
dc.identifier.scopus | eid_2-s2.0-42149163701 | en_HK |
dc.identifier.hkuros | 149017 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-42149163701&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 114 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 321 | en_HK |
dc.identifier.epage | 334 | en_HK |
dc.identifier.eissn | 1436-4646 | - |
dc.identifier.isi | WOS:000254805300006 | - |
dc.publisher.place | Germany | en_HK |
dc.identifier.scopusauthorid | Ding, G=7201791806 | en_HK |
dc.identifier.scopusauthorid | Feng, L=55231207200 | en_HK |
dc.identifier.scopusauthorid | Zang, W=7005740804 | en_HK |
dc.identifier.issnl | 0025-5610 | - |