Computer Science/Discrete Mathematics Seminar II

We present the Controlled Linear Programming Problem (CLPP), a new combinatorial optimization problem nicely merging linear programming with games. In a system of linear monotone constraints of the form $x_i\leq p_i^j(\bar x)+w_i^j$, where $p_i^j$ are linear homogeneous polynomials with nonnegative coefficients and $w_i^j\in\mathbb R$, some variables are distinguished as \emph{controlled} and we want to select \emph{exactly one} constraint for each controlled variable to make $\max\sum x_i$, subject to the remaining constraints, as large as possible (over all possible such selections). We suggest a number of iterative strategy improvement policies, simplex-like and interior-point. For many important cases we prove optimality conditions (when a local optimum is global), describe a number of combinatorial randomized \emph{subexponential} algorithms, and show that the decision version of the problem is in NP $\cap$ coNP. It turns out that the well-known mean payoff, discounted payoff, simple stochastic, and parity games, as well as the recent Longest-Shortest Paths (LSP) problem [MFCS'2004] (all in NP $\cap$ coNP, unknown to be in P) are easily reducible to the CLPP. This suggests a simplifying and unifying view of all these games as particular restricted instances of the CLPP, one of the ``most general'' problems in NP $\cap$ coNP to which all the known games in the class reduce (in certain sense ``complete'' in the class). We show that a slight generalization of the CLPP allowing for negative coefficients in the constraint polynomials $p_i^j$ is NP-hard. So are the controlled versions of many other polynomial optimization problems, like \textsc{Maximum Flow}. The simple algebraic and combinatorial structure of the CLPP unifies and gives insights into algorithmic and complexity-theoretic studies of infinite games, and is amenable to the powerful tools from combinatorial and polyhedral optimization, as well as linear programming. In this paper we investigate boundedness, CLPP duality, stability, optimality conditions, correctness of subexponential algorithms, and conditions for NP$\cap$coNP-membership. In particular, strong duality immediately implies NP $\cap$ coNP-membership, polynomial optimality conditions, and strongly subexponential algorithms. We also describe new pseudopolynomial and subexponential algorithms for \emph{Mean Payoff Games} (MPGs). The algorithms are based on representing the MPG decision problem in the forms of non-standard and standard \emph{Linear Complementarity Problems} (LCPs): find $w,z\geq 0$ satisfying $w=Mz+q$ and $w^T\cdot z=0$, and monotonic iterative propagation of slack updates.