Source author record

Lorenz Klaus

Lorenz Klaus appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO math.OC Computational Complexity Discrete Mathematics

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

A Strongly Polynomial Reduction for Linear Programs over Grids

We investigate the duality relation between linear programs over grids (Grid-LPs) and generalized linear complementarity problems (GLCPs) with hidden K-matrices. The two problems, moreover, share their combinatorial structure with discounted Markov decision processes (MDPs). Through proposing reduction schemes for the GLCP, we obtain a strongly polynomial reduction from Grid-LPs to linear programs over cubes (Cube-LPs). As an application, we obtain a scheme to reduce discounted MDPs to their binary counterparts. This result also suggests that Cube-LPs are the key problems with respect to solvability of linear programming in strongly polynomial time. We then consider two-player stochastic games with perfect information as a natural generalization of discounted MDPs. We identify the subclass of the GLCPs with P-matrices that corresponds to these games and also provide a characterization in terms of unique-sink orientations. A strongly polynomial reduction from the games to their binary counterparts is obtained through a generalization of our reduction for Grid-LPs.

preprint2014arXiv

Enumeration of PLCP-orientations of the 4-cube

The linear complementarity problem (LCP) provides a unified approach to many problems such as linear programs, convex quadratic programs, and bimatrix games. The general LCP is known to be NP-hard, but there are some promising results that suggest the possibility that the LCP with a P-matrix (PLCP) may be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains open. Simple principal pivoting (SPP) algorithms, also known as Bard-type algorithms, are candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted SPP algorithms as a family of algorithms that seek the sink of unique-sink orientations of $n$-cubes. They performed the enumeration of the arising orientations of the $3$-cube, hereafter called PLCP-orientations. In this paper, we present the enumeration of PLCP-orientations of the $4$-cube.The enumeration is done via construction of oriented matroids generalizing P-matrices and realizability classification of oriented matroids.Some insights obtained in the computational experiments are presented as well.

preprint2013arXiv

Counting Unique-Sink Orientations

Unique-sink orientations (USOs) are an abstract class of orientations of the n-cube graph. We consider some classes of USOs that are of interest in connection with the linear complementarity problem. We summarise old and show new lower and upper bounds on the sizes of some such classes. Furthermore, we provide a characterisation of K-matrices in terms of their corresponding USOs.

preprint2010arXiv

Combinatorial Characterizations of K-matrices

We present a number of combinatorial characterizations of K-matrices. This extends a theorem of Fiedler and Ptak on linear-algebraic characterizations of K-matrices to the setting of oriented matroids. Our proof is elementary and simplifies the original proof substantially by exploiting the duality of oriented matroids. As an application, we show that a simple principal pivot method applied to the linear complementarity problems with K-matrices converges very quickly, by a purely combinatorial argument.