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

**Martijn van Brink**

Express delivery of packages

**Coauthors: Alexander Grigoriev, Tjark Vredeveld**

**Abstract:**

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"** [...]