1 citations · 1 across the 5 of their papers we have counts for
10 papers
Exact Price of Anarchy for Weighted Congestion Games with Two Players
Joran van den Bosse, Marc Uetz, Matthias Walter
This paper gives a complete analysis of worst-case equilibria for various versions of weighted congestion games with two players and affine cost functions. The results are exact pr…
The Graphical Traveling Salesperson Problem has no Integer Programming Formulation in the Original Space
Matthias Walter
The Graphical Traveling Salesperson Problem (GTSP) is the problem of assigning, for a given weighted graph, a nonnegative number each edge such that the induced multi-sub…
Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs
Matthias Walter
Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they…
Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials
Christopher Hojny, Marc E. Pfetsch, Matthias Walter
Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given pol…
Persistency of Linear Programming Relaxations for the Stable Set Problem
Elisabeth Rodríguez-Heck, Karl Stickler, Matthias Walter +1
The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: f…
The Almost-Disjoint 2-Path Decomposition Problem
Annika Thome, Matthias Walter
We consider the problem of decomposing a given (di)graph into paths of length 2 with the additional restriction that no two such paths may have more than one vertex in common. We e…