论文标题
几何独特的水槽方向的新组合特性
A New Combinatorial Property of Geometric Unique Sink Orientations
论文作者
论文摘要
独特的下水道方向（USO）是HyperCube图的方向，每个脸部都有独特的水槽。许多认真的问题减少了在多项式时间内找到USO的全球水槽；最值得注意的是，线性编程（LP）和P-Matrix线性互补问题（P-LCP）。众所周知，前者具有强烈的多项式算法，而后者甚至没有具有多项式时间算法，激发了该问题以找到USO的全局水槽。虽然，相对于所有USOS的类别，由LP等具体问题（例如LP）产生的每一类已知的几何USO都呈指数级小。因此，几何USO具有其他属性，使它们与普通USO区分开，如果不需要，则可以利用这些属性来更快地找到USO的全局水槽。只有少数此类属性是已知的。在本文中，我们建立了由对称P-LCP引起的USO的新组合属性，其中包括由线性和简单凸二次编程产生的USOS。
A unique sink orientation (USO) is an orientation of the hypercube graph with the property that every face has a unique sink. A number of well-studied problems reduce in strongly polynomial time to finding the global sink of a USO; most notably, linear programming (LP) and the P-matrix linear complementarity problem (P-LCP). The former is not known to have a strongly polynomial-time algorithm, while the latter is not known to even have a polynomial-time algorithm, motivating the problem to find the global sink of a USO. Although, every known class of geometric USOs, arising from a concrete problem such as LP, is exponentially small, relative to the class of all USOs. Accordingly, geometric USOs exhibit additional properties that set them apart from general USOs, and it may be advantageous, if not necessary, to leverage these properties to find the global sink of a USO faster. Only a few such properties are known. In this paper, we establish a new combinatorial property of the USOs that arise from symmetric P-LCP, which includes the USOs that arise from linear and simple convex quadratic programming.
