2014/05/08 by Lorenz Klaus, Klaus, Lorenz
Computer Science · Mathematics · #90C05 #90C27 #90C33 #90C40 #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1405.1827
openalex publication_date 2014/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.