The complexity of recognizing linear systems with certain integrality properties期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

The complexity of recognizing linear systems with certain integrality properties

Authors:	Guoli Ding Li Feng Wenan Zang

Institution:	(1) Mathematics Department, Louisiana State University, Baton Rouge, LA 70803-4918, USA;(2) Department of Mathematics, The University of Hong Kong, Hong Kong, China

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. Supported in part by NSA grant H98230-05-1-0081 and NSF grants DMS-0556091 and ITR-0326387. Supported in part by the Research Grants Council of Hong Kong and Seed Funding for Basic Research of HKU.

Keywords:	Linear system Polyhedron Total dual integrality NP-hardness
本文献已被 SpringerLink 等数据库收录！