Summer Paper Proposals from:
Vineet Goyal, Viswanath Nagarajan, Mohit Singh, and John Turner
Tepper School of Business
Friday, May 13, 2005
2:00 - 3:30 pm
384 Posner Hall
Abstracts:
Approximation Algorithms for Demand-Robust Covering Problems
Vineet Goyal
Robust optimization has traditionally focused on uncertainty in data and
costs in optimization problems to formulate models whose solutions will be
optimal in the worst-case among the various uncertain scenarios in the
model. While these approaches may be thought of defining data- or
cost-robust problems, we formulate a new “demand-robust” model motivated by
recent work on two-stage stochastic optimization problems. We propose this
in the framework of general covering problems and prove a general
structural lemma about special types of first-stage solutions for such
problems: There exist a first-stage solution that is feasible for the union
of the demands for some subset of the scenarios whose objective function
value is no more than twice the optimal.
We consider the shortest path and steiner tree problems in the
demand-robust setting. We currently have a 16-approximation for these
problems. We hope to obtain better approximation ratios for the problem
using the structural lemma. Other problems that we plan to address are
Vertex Cover, Facility Location.
In this talk, I would present some preliminary ideas in the direction of
obtaining approximation algorithms for the above mentioned problems.
Approximation Algorithms for Vehicle Routing with time windows
Viswanath Nagarajan
Vehicle routing problems are extensively studied in the operations research
literature. Several good heuristics have been proposed for these problems,
but there are not many approximation guarantees. The goal of this summer
paper is to come up with approximation algorithms for some vehicle routing
problems. The general problem we plan to look at is vehicle routing with
time windows: Given a graph G with a source vertex s, an allowed time
window for each vertex, and a certain number k of vehicles that ply from s,
find a route for each vehicle such that every vertex is visited in its time
window by some vehicle. We can formulate different optimization problems
depending on the objective. As a first step we try to minimize the number
of vehicles. There has been some recent work on approximation algorithms
for vehicle routing. In this talk, I will mention these results and show
how they are relevant to our problem.
Improved Approximation Algorithms for Minimum Degree Minimum
Spanning Tree Problem
Mohit Singh
Minimum Degree Minimum Spanning Tree (MDMST) Problem is a fundamental
network design problem. In an instance of MDMST problem, given a graph G =
(V,E) and a cost function c on edges, we ask for a minimum spanning tree
whose maximum degree is minimized. Here, the maximum degree of a tree is
the maximum degree of any node in the tree. This problem is NP-hard and
best polynomial time approximation algorithm is due to Fischer which
returns an MST of maximum degree at most b__ + logb n for any b > 1. Here,
__ is the maximum degree of the optimum MST.
We plan to obtain an improved polynomial approximation algorithm which
returns an MST of maximum degree at most __ +1. The road map is to
non-constructively prove that a natural lower-bound is within one of the
optimal and then convert the proof into a polynomial time algorithm. This
plan is similar to the one followed for the case when all costs are
identical.
We also plan to consider the Bounded Degree Minimum Spanning Tree
problem(BDMST), where we are also given degree bound Bv for vertex v and we
demand a spanning tree of minimum cost satisfying the degree bounds.
Bi-criteria approximation algorithm for this problem has been considered in
Ravi and Konemann.
Robust Solutions of the Resource-Constrained Project Scheduling Problem
John Turner
In this paper we will attempt to find robust solutions for the
Resource-Constrained Project Scheduling Problem (RCPSP).
Given a set of n jobs with deterministic processing times {di, i = 1..n}, a
solution of the
RCPSP is an integer-valued vector s where si is the start time of the ith
job (we assume time is discrete and preemptions are not allowed).
There are two types of constraints: temporal constraints and resource
constraints. To get a robust solution to the RCPSP, it was suggested that
instead of computing a single solution vector s, one should produce a set S
of solutions from which a particular solution may be selected at runtime.
Since computing the minimum-makespan schedule is easy if no resource
constraints exist, a natural way to define the set S is to start with an
instance of RCPSP and to introduce precedence constraints of the form si _
sj which make the resource constraints redundant. The solution space of
this new problem is S. Maximizing robustness reduces to finding a set of
precedence constraints that maximizes |S| (the size of the feasible region
of the polyhedron defined by the temporal constraints and the introduced
precedence constraints).
Previous work employs heuristic search to try and find good solutions S to
this problem. We hope to extend the results in this area by finding a
characterization of the optimal solution. Some techniques that may be
employed include edge finding, exploiting properties of partiallyordered
sets, and approximating volumes of polyhedra.
