Double EADS-talk by Katarzyna Paluch & Matthias Mnich – University of Copenhagen

Double EADS-talk by Katarzyna Paluch & Matthias Mnich

Katarzyna Paluch, 16.15-16.45:

Maximum ATSP with weights zero and one via half-edges

We present a fast combinatorial $3/4$-approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this algorithm matches the currently best one given by Bl{\"a}ser in 2004 and based on linear programming. Our algorithm first computes a maximum size matching and a maximum weight cycle cover without certain cycles of length two but possibly with {\em half-edges} - a half-edge of a given edge $e$ is informally speaking a half of $e$ that contains one of the endpoints of $e$. Then from the computed matching and cycle cover it extracts a set of paths, whose weight is large enough to be able to construct a traveling salesman tour with the claimed guarantee.

Matthias Mnich, 16.50-17.20:

On Routing Disjoint Paths in Bounded Treewidth Graphs

We study the problem of routing on disjoint paths in bounded treewidth  graphs with both edge and node capacities. The input consists of a  capacitated graph G = (V,E) and a collection of k source-destination pairs M = {(s_1 ,t_1 ),...,(s_k ,t_k)}. The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset M' of the pairs is a collection P of paths such that, for each pair (s_i ,t_i ) \in M', there is a path in P connecting s i to t i . In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph G has capacities cap(e) on the edges and a routing P is feasible if each edge e is in at most cap(e) of the paths of P. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP.

We obtain an O(r^3) approximation for MaxEDP on graphs of treewidth at most r and a matching approximation for MaxNDP on graphs of pathwidth at most r. Our results build on and significantly improve the work of [Chekuri et al. ICALP 2013] that obtained an O(r · 3^r ) approximation for MaxEDP.