Abstract:
We study three methods based on linear programming and generalizations
that are often applied to approximate combinatorial optimization
problems.
We start by describing an approximate method based on linear
programming;
as an example we consider scheduling of jobs on unrelated machines with
costs.
The second method presented is based on semidefinite programming; we
show
how to obtain a reasonable solution for the maximum cut problem.
Finally, we analyze the conditional probabilities method in connection
with randomized rounding for routing, packing and covering
integer linear programming problems.
CV:
Jose Rolim. Professor and Head of the Theoretical Computer
Science
Group at the University of Geneva. PhD by the University of
California,
1986. Chair of Irregular, Random and IPPS conferences, European
representative of the IEEE TC on Parallel Processing. Research
interests
on randomized computation, derandomization methods and parallel
processing.