An analysis of selected F -quantified linear programs

In this paper, we discuss new results on feasibility checking in a specialized class of Quantified Linear Programs (QLPs), called F-QLPs. Quantified linear programming is a two player generalization of linear programming. In traditional linear programming, there is a single player who chooses the values of the variables associated with each column. In quantified linear programming, the program variables are partitioned into two sets and each player controls one set. Specifically, the variables are partitioned into existentially quantified variables and universally quantified variables. The complexity of the game depends upon the order in which the moves of the two players are specified. F-QLPs are a specialized class of QLPs in which the universal player has to make all his moves before the existential player makes a single move. Previous research has established that the problem of checking F-QLP feasibility is coNP-complete. In this paper, we discuss two new results, viz., (a) a certifying polynomial time algorithm for a subclass of F-QLPs called F-QLPPL, and (b) a proof of coNP-completeness for the F-QLP optimization problem over totally unimodular matrices.