Friday, 10:30 - 10:55 h, Room: H 3010


Martijn van Brink
Express delivery of packages

Coauthors: Alexander Grigoriev, Tjark Vredeveld


We consider a capacitated, fixed-charge, multicommodity flow problem with indivisible commodities. The commodities are transported with trucks, which all have the same capacity, and we assume there is an unlimited number of trucks. We show that, unless P=NP, there cannot exist a polynomial time O(log K)- approximation algorithm, where K is the number of commodities. Applying randomized rounding, we obtain an approximation ratio of K+1, and we show that this ratio is tight. Next, we restrict the underlying network to cycles. We prove that the problem remains NP-hard and we develop a 4-approximation. If we assume that the total volume of all commodities is at most the capacity of a single truck, we get an integer linear programming formulation with a totally unimodular constraint matrix. Thus, we can obtain the optimal solution in polynomial time. Finally, we consider the case where we have a fixed number of commodities, and show that for 2 and 3 commodities the problem can be also solved in polynomial time.


Talk 1 of the contributed session Fri.1.H 3010
"Approximation of vehicle routing problems" [...]
Cluster 1
"Approximation & online algorithms" [...]


  Florida Payday Loans can help you in trying times, but be sure to know the laws necessary for your loan application. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.