Cost allocation: the traveling salesman, binpacking, and the knapsack

摘要

We examine the problem of cost allocation for the traveling-salesman problem (TSP). We note the significance of a “home” city in the TSP for designing cost allocation schemes, focusing on TSPs with triangular inequality. In addition, a similar cost allocation question is stated for the binpacking and the knapsack problems.