Sign-Solvability of Linear Programming and Linear Complementarity Problems
Speaker: | Naonori Kakimura |
---|---|
Affiliation: | University of Tokyo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
This
talk
presents
an
attempt
to
connect
qualitative
matrix
theory
with
linear
programming
and
linear
complementarity
problems.
A
linear
program
max{cx
|
Ax=b,
x>=0}
is
said
to
be
sign-solvable
if
the
set
of
sign
patterns
of
the
optimal
solutions
is
uniquely
determined
by
the
sign
patterns
of
A,
b,
and
c.
Checking
the
sign-solvability
of
a
given
linear
program
turns
out
to
be
co-NP-complete.
We
then
introduce
a
class
of
sign-solvable
linear
programs
in
terms
of
totally
sign-nonsingular
matrices,
which
can
be
recognized
in
polynomial
time.
For
a
linear
program
in
this
class,
we
devise
an
efficient
combinatorial
algorithm
to
obtain
the
sign
pattern
of
an
optimal
solution
from
the
sign
patterns
of
A,
b,
and
c.
Similarly,
we
introduce
sign-solvability
for
linear
complementarity
problems
(LCPs).
We
show
that
a
totally
sign-nonsingular
matrix
characterizes
a
sign-solvable
LCP
whose
coefficient
matrix
is
nonzero
diagonal.
This
characterization
leads
to
an
efficient
algorithm
to
obtain
the
sign
pattern
of
a
solution
for
these
LCPs.
The first part of this talk is a joint work with Satoru Iwata.
References:
S. Iwata and N. Kakimura: Solving Linear Programs from Sign Patterns, Mathematical Programming, to appear.
N. Kakimura: Sign-Solvable Linear Complementarity Problems, Lecture Notes in Computer Science, Springer-Verlag 4513, pp.397--409, 2007.