File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: The complexity of recognizing linear systems with certain integrality properties

TitleThe complexity of recognizing linear systems with certain integrality properties
Authors
Ding, GFeng, LZang, W
KeywordsLinear system
NP-hardness
Polyhedron
Total dual integrality
Issue Date2008
PublisherSpringer 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?
DOI: http://dx.doi.org/10.1007/s10107-007-0103-y
AbstractLet 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 Identifierhttp://hdl.handle.net/10722/58972
ISSN
0025-5610
2021 Impact Factor: 3.060
2020 SCImago Journal Rankings: 2.358
ISI Accession Number ID
WOS:000254805300006
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorDing, Gen_HK
dc.contributor.authorFeng, Len_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-05-31T03:40:36Z-
dc.date.available2010-05-31T03:40:36Z-
dc.date.issued2008en_HK
dc.identifier.citationMathematical Programming, 2008, v. 114 n. 2, p. 321-334en_HK
dc.identifier.issn0025-5610en_HK
dc.identifier.urihttp://hdl.handle.net/10722/58972-
dc.description.abstractLet 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.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/10107/en_HK
dc.relation.ispartofMathematical Programmingen_HK
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectLinear systemen_HK
dc.subjectNP-hardnessen_HK
dc.subjectPolyhedronen_HK
dc.subjectTotal dual integralityen_HK
dc.titleThe complexity of recognizing linear systems with certain integrality propertiesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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+Propertiesen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturepreprint-
dc.identifier.doi10.1007/s10107-007-0103-yen_HK
dc.identifier.scopuseid_2-s2.0-42149163701en_HK
dc.identifier.hkuros149017en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-42149163701&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume114en_HK
dc.identifier.issue2en_HK
dc.identifier.spage321en_HK
dc.identifier.epage334en_HK
dc.identifier.eissn1436-4646-
dc.identifier.isiWOS:000254805300006-
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridDing, G=7201791806en_HK
dc.identifier.scopusauthoridFeng, L=55231207200en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0025-5610-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats