|
|||||
|
|
Optimization with binet matrices |
|
| Authors: | Gautam Appa Balázs Kotnyek Leonidas Pitsoulis |
| Institution: | a Operational Research Department, London School of Economics, Houghton Street, London WC2A 2AE, UK b I3S & Inria Sophia Antipolis, France c Department of Mathematical and Physical Sciences, Aristotle University of Thessaloniki, Thessaloniki 54124, Greece |
| Abstract: | This paper deals with linear and integer programming problems in which the constraint matrix is a binet matrix. Linear programs can be solved with the generalized network simplex method, while integer programs are converted to a matching problem. It is also proved that an integral binet matrix has strong Chvátal rank 1. |
| Keywords: | Half-integrality Generalized networks Matching Strong Chvá tal rank |
| 本文献已被 ScienceDirect 等数据库收录！ | |