10 citations · 14 across the 14 of their papers we have counts for
19 papers
Algorithmic Solutions for Maximizing Shareable Costs
Rong Zou, Boyue Lin, Marc Uetz +1
This paper addresses the optimization problem to maximize the total costs that can be shared among a group of agents, while maintaining stability in the sense of the core constrain…
The Binary Linearization Complexity of Pseudo-Boolean Functions
Matthias Walter
We consider the problem of linearizing a pseudo-Boolean function by means of Boolean functions. Such a linearization yields an integer linear pro…
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…
Recognizing Series-Parallel Matrices in Linear Time
Matthias Walter
A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are parallel to an existing row/column or have…
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…
A Polyhedral Study for the Cubic Formulation of the Unconstrained Traveling Tournament Problem
Marije Siemann, Matthias Walter
We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research…
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…
Extended Formulations for Radial Cones
Matthias Walter, Stefan Weltge
This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron at a vertex is the polyhedron defined by…
Parity Polytopes and Binarization
Dominik Ermel, Matthias Walter
We consider generalizations of parity polytopes whose variables, in addition to a parity constraint, satisfy certain ordering constraints. More precisely, the variable domain is pa…
A Note on Matchings Constructed during Edmonds' Weighted Perfect Matching Algorithm
Volker Kaibel, Matthias Walter
We reprove that all the matchings constructed during Edmonds' weighted perfect matching algorithm are optimal among those of the same cardinality (provided that certain mild restri…
Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs
Matthias Walter
We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of all matchings, extended by a binary entry indicating whether the matching contains two spe…
Extended Formulations for Independence Polytopes of Regular Matroids
Volker Kaibel, Jon Lee, Matthias Walter +1
The ancillary file Corrigendum.pdf contains an explanation why our proof does not work.
Subgraph Polytopes and Independence Polytopes of Count Matroids
Michele Conforti, Volker Kaibel, Matthias Walter +1
Given an undirected graph, the non-empty subgraph polytope is the convex hull of the characteristic vectors of pairs (F, S) where S is a non-empty subset of nodes and F is a subset…
On a Cardinality-Constrained Transportation Problem With Market Choice
Pelin Damci-Kurt, Santanu S. Dey, Simge Kucukyavuz
It is well-known that the intersection of the matching polytope with a cardinality constraint is integral [8]. We prove a similar result for the polytope corresponding to the trans…
Simple Extensions of Polytopes
Volker Kaibel, Matthias Walter
We introduce the simple extension complexity of a polytope P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which…
Implementation of a Unimodularity Test
Matthias Walter, Klaus Truemper
This paper describes implementation and computational results of a polynomial test of total unimodularity. The test is a simplified version of a prior method. The program also deci…