Friday, September 9, 2005
2:00 - 3:30 pm
388 Posner Hall
Minimum vehicle routing with a common deadline
Viswanath Nagarajan
Tepper School of Business
An important version of vehicle routing problems involves customer deadlines
and having to service all of them even though it may require many vehicles
to do so. Motivated by such applications, we study approximation algorithms
for the following NP-hard variant: the input to our problem consists of $n$
vertices in a metric space, a specified root vertex $r$, and a length bound
$D$. The goal is to cover all the vertices, using the minimum number of
$r$-paths, each of length at most $D$. On general metrics, we obtain an
$O(\log D)$ approximation algorithm for this problem. When restricted to
tree metrics, we obtain an improved 4-approximation algorithm. Both these
algorithms have a running time that is almost linear in the size of the
input. We also obtain tight bounds on the quality of a candidate lower bound
based on clumping, for general metrics.
On Minimum Degree Minimum Spanning Tree Problem
Mohit Singh
Tepper School of Business
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. As the problem is NP-hard, we aim
obtain the near best algorithm which returns a MST with maximum
degree $OPT+1$ while the best known result due to Fischer returns
an MST of maximum degree at most $O(OPT+\log n)$. Here, $OPT$
is the maximum degree of the optimum MST.
In my proposal, we presented a non-constructive optimal swap
theorem and a conjecture motivated by the theorem and previous
results. In this paper, we extend the known results which leads us
to a different conjecture. I will also present a roadmap of how
we plan to prove the new conjecture.
This is ongoing work with R. Ravi.
