## Invited Session Mon.3.H 3021

#### Monday, 15:15 - 16:45 h, Room: H 3021

**Cluster 2: Combinatorial optimization** [...]

### Equilibria and combinatorial structures

**Chair: Britta Peis**

**Monday, 15:15 - 15:40 h, Room: H 3021, Talk 1**

**Walter Kern**

Cooperative games and fractional programming

**Abstract:**

Straightforward analysis of core-related optimization problems leads to interesting fractional versions of standard (combinatorial) optimization problems and challenging open conjectures. We focus on two particular cases: TSP and bin packing.

**Monday, 15:45 - 16:10 h, Room: H 3021, Talk 2**

**Tamás Király**

Multiplayer multicommodity flows

**Coauthors: Attila Bernáth, Mádi-Nagy Gergely, Pap Gyula, Pap Júlia**

**Abstract:**

We investigate the Multiplayer Multicommodity Flow Problem, a version of the multicommodity flow problem where players have different subnetworks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value.

We show that the social optimum can be computed by linear programming. In contrast, an equilibrium solution, although it always exists under some natural conditions, is PPAD-hard to find. We analyze hardness in relation to the structure of the digraph formed by the contracts between players, and prove that an equilibrium can be found in polynomial time if every strongly connected component of this digraph is a cycle.

**Monday, 16:15 - 16:40 h, Room: H 3021, Talk 3**

**Tom McCormick**

A primal-dual algorithm for weighted abstract cut packing

**Coauthor: Britta Peis**

**Abstract:**

Hoffman and Schwartz developed the Lattice Polyhedron model and proved that it is totally dual integral (TDI), and so has integral optimal solutions. The model generalizes many important combinatorial optimization problems such as polymatroid intersection, cut covering polyhedra, min cost aborescences, etc., but has lacked a combinatorial algorithm. The problem can be seen as the blocking dual of Hoffman's Weighted Abstract Flow (WAF) model, or as an abstraction of ordinary Shortest Path and its cut packing dual, so we call it Weighted Abstract Cut Packing (WACP). We develop the first combinatorial algorithm for WACP, based on the Primal-Dual Algorithm framework. The framework is similar to that used by Martens and McCormick for WAF, in that both algorithms depend on a relaxation by a scalar parameter, and then need to solve an unweighted "restricted'' subproblem. The WACP subroutine uses an oracle to solve a restricted abstract cut packing/shortest path subproblem using greedy cut packing, breadth-first search, and an update that achieves complementary slackness. This plus a standard scaling technique yields a polynomial combinatorial algorithm.