<p>The study of the combinatorial diameter of a polyhedron is a classical topic in linear-programming theory due to its close connection with the possibility of a polynomial-time simplex-method pivot rule. The 2-sum operation is a classical operation for graphs, matrices, and matroids, giving a natural way to link combinatorial systems. In particular, the 2-sum also appears as a key operation in Seymour’s decomposition theorem for totally-unimodular matrices. We extend the definition of 2-sum to standard-form polyhedra, which is quite natural given the link between systems of linear equations and representable matroids. In linear and integer-programming, these 2-sum polyhedra give a natural way to link two systems in a joint model with a single shared constraint. We analyze the diameters of polyhedra that arise from this 2-sum operation. We demonstrate that the diameter of a 2-sum polyhedron is quadratic in the diameters of its summands. The methods transfer to a linear bound for the addition of a unit column to an equality system, or equivalently, to the relaxation of an equality constraint to an inequality constraint. Furthermore, we use our methods to analyze the distance between vertices on certain faces of a 3-sum polyhedron.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the diameter of a 2-sum of polyhedra

  • Steffen Borgwardt,
  • Weston Grewe,
  • Jon Lee

摘要

The study of the combinatorial diameter of a polyhedron is a classical topic in linear-programming theory due to its close connection with the possibility of a polynomial-time simplex-method pivot rule. The 2-sum operation is a classical operation for graphs, matrices, and matroids, giving a natural way to link combinatorial systems. In particular, the 2-sum also appears as a key operation in Seymour’s decomposition theorem for totally-unimodular matrices. We extend the definition of 2-sum to standard-form polyhedra, which is quite natural given the link between systems of linear equations and representable matroids. In linear and integer-programming, these 2-sum polyhedra give a natural way to link two systems in a joint model with a single shared constraint. We analyze the diameters of polyhedra that arise from this 2-sum operation. We demonstrate that the diameter of a 2-sum polyhedron is quadratic in the diameters of its summands. The methods transfer to a linear bound for the addition of a unit column to an equality system, or equivalently, to the relaxation of an equality constraint to an inequality constraint. Furthermore, we use our methods to analyze the distance between vertices on certain faces of a 3-sum polyhedron.