abstract
the problem of detecting and removing redundant constraints is fundamental in
optimization. we focus on the case of linear programs (lps), given by d variables
with n inequality constraints. a constraint is called redundant, if after its removal,
the lp still has the same feasible region. the currently fastest method to detect all
redundancies is due to clarkson: it solves n linear programs, but each of them has
at most s constraints, where s is the number of nonredundant constraints.
in this paper, we study the special case where every constraint has at most two
variables with nonzero coefficients. this family, denoted by li(2), has some nice
properties. namely, as shown by aspvall and shiloach, given a variable xi and a
value λ, we can test in time o(nd) whether there is a feasible solution with xi = λ.
hochbaum and naor present an o(d2 n log n) algorithm for solving the feasibility
problem in li(2). their technique makes use of the fourier-motzkin elimination
method and the earlier mentioned result by aspvall and shiloach.
we present a strongly polynomial algorithm that solves redundancy detection in
time o(nd2 s log s). it uses a modification of clarkson’s algorithm, together with a
revised version of hochbaum and naor’s technique. finally we show that dimensionality testing can be done with the same running time as solving feasibility.