Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, May 30, 2011

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

David P. Williamson - Cornell University and TU Berlin

The Subtour LP for the Traveling Salesman Problem

The traveling salesman problem (TSP) is the most famous problem in discrete optimization. Given $n$ cities and the costs $c_{ij}$ for traveling from city $i$ to city $j$ for all $i,j$, the goal of the problem is to find the least expensive tour that visits each city exactly once and returns to its starting point. We consider cases in which the costs are symmetric and obey the triangle inequality. In 1954, Dantzig, Fulkerson, and Johnson introduced a linear programming relaxation of the TSP now known as the subtour LP, and used it to find the optimal solution to a 48-city instance. Ever since then, the subtour LP has been used extensively to find optimal solutions to TSP instances, and it is known to give extremely good lower bounds on the length of an optimal tour.
Nevertheless, the quality of the subtour LP bound is poorly understood from a theoretical point of view. For 30 years it has been known that it is at least 2/3 times the length of an optimal tour for all instances of the problem, and it is known that there are instances such that it is at most 3/4 times the length of an optimal tour, but no progress has been made in 30 years in tightening these bounds.
In this talk we will review some of the results that are known about the subtour LP, and give some new results that refine our understanding in some cases. In particular, we have been able to make some progress in resolving a conjecture of Boyd and Carr about the ratio of an optimal 2-matching to the subtour LP bound in the worst case. We also begin a study of the subtour LP bound for the extremely simple case in which all costs $c_{ij}$ are either 1 or 2. For these instances we can show that the subtour LP is always strictly better than 3/4 times the length of an optimal tour.
These results are joint work with Jiawei Qian, Frans Schalekamp, and Anke van Zuylen.

Colloquium - 16:00

Tobias Harks - TU Berlin

Scalable Cost-Sharing in Resource Allocation Games

Resource allocation problems play a key role in many applications, including traffic networks, telecommunication networks and economics. In most applications, the allocation of resources is determined by a finite number of players, each optimizing an individual objective function. An important question in all these applications is the degree of suboptimality caused by sel fish resource allocation. Because the set of Nash equilibria of a resource allocation game depends on the cost sharing methods used, I will first introduce the fundamental problem of designing a cost sharing method so as to minimize the worst-case efficiency loss. Then I will present a generic upper bound on the worst-case efficiency loss for a class of cost sharing methods used in practice. The power of this bound is demonstrated by applying it to three well known cost sharing methods: incremental cost sharing, marginal cost pricing, and average cost sharing.

Letzte Aktualisierung: 16.05.2011