Events & News
Colloquium
| Category | Lecture |
| Date | Tuesday, March 2, 2010 |
| Time | 11:00 am |
| Location | GS 906 |
| Details | Light refreshments - 9th floor Atrium - 10:45 am |
| Speaker | Aparna Das |
| Title | PhD Student |
| Affiliation | Brown University - Providence, RI |
Approximation schemes for the vehicle routing problem with unsplittable demands.
Abstract: Vehicles routing describes a class of optimization problems where the objective is to find low cost delivery routes from a central depot to customers using vehicles of limited capacity. These problems generalize the traveling salesman problem and have many real world applications to businesses where transportation costs matter, such as UPS, waste removal companies, and food and beverage distributors.
We study the vehicle routing problem with unsplittable demands where
each customer's entire demand must be delivered at one time and may not
be split up among multiple delivery routes. The problem is strongly
NP-Hard and cannot be approximated better than 3/2. However we design
polynomial time approximation schemes for two special settings that
approximate the problem within factor (1+c) for any c >0. The first is
the asymptotic setting where the optimal solution is big. The second
setting is when K, the input parameter that corresponds to the vehicle
capacity, is polynomial in the number of customers.
This is joint work with Claire Mathieu and Shay Mozes.
Biography