Name
Abstract | ||
|---|---|---|
We consider the train delivery problem which is a generalization of the bin packing problem and is equivalent to a one dimensional version of the vehicle routing problem with unsplittable demands. The problem is also equivalent to the problem of minimizing the makespan on a single batch machine with non-identical job sizes. The train delivery problem is strongly NP-hard and does not admit an approximation ratio better than 3/2. We design the first approximation schemes for the general problem. We give an asymptotic polynomial time approximation scheme, under a notion of asymptotic that makes sense even though scaling can cause the cost of the optimal solution of any instance to be arbitrarily large. Alternatively, we give a polynomial time approximation scheme for the case where W, an input parameter that corresponds to the bin size or the vehicle capacity, is polynomial in the number of items or demands. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-18318-8_9 | WAOA |
Keywords | Field | DocType |
dimensional version,polynomial time approximation scheme,approximation ratio,general problem,approximation scheme,bin packing problem,bin size,asymptotic polynomial time approximation,train delivery problem,vehicle routing,vehicle capacity,bin packing,vehicle routing problem | Partition problem,Combinatorics,Mathematical optimization,Vehicle routing problem,Job shop scheduling,Computer science,Function problem,Cutting stock problem,Multi-commodity flow problem,Polynomial-time approximation scheme,Bin packing problem | Conference |
Volume | ISSN | Citations |
6534 | 0302-9743 | 4 |
PageRank | References | Authors |
0.43 | 21 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aparna Das | 1 | 98 | 7.66 |
| Claire Mathieu | 2 | 452 | 25.78 |
| Shay Mozes | 3 | 292 | 22.87 |