6 citations · 17 across the 16 of their papers we have counts for
28 papers
Reconstruction of C_4-free graphs from the set of closed neighborhoods and digital convexity
Steffen Borgwardt, MacKenzie Carr, Ce Chen +4
Fomin, Kratochvíl, Lokshtanov, Mancini, and Telle showed that every -free graph is reconstructible from the \emph{multiset} of closed neighborhoods. We strengthen their resu…
Path Odd-Covers of Graphs
Steffen Borgwardt, Calum Buchanan, Eric Culver +3
We introduce and study "path odd-covers", a weakening of Gallai's path decomposition problem and a strengthening of the linear arboricity problem. The "path odd-cover number" $p_2(…
On the Circuit Diameter Conjecture for Counterexamples to the Hirsch Conjecture
Alexander E. Black, Steffen Borgwardt, Matthias Brugger
Circuit diameters of polyhedra are a fundamental tool for studying the complexity of circuit augmentation schemes for linear programming and for finding lower bounds on combinatori…
An Integer Program for Pricing Support Points of Exact Barycenters
Steffen Borgwardt, Stephan Patterson
The computation of exact barycenters for a set of discrete measures is of interest in applications where sparse solutions are desired, and to assess the quality of solutions return…
Circuits in Extended Formulations
Steffen Borgwardt, Matthias Brugger
Circuits and extended formulations are classical concepts in linear programming theory. The circuits of a polyhedron are the elementary difference vectors between feasible points a…
On the Combinatorial Diameters of Parallel and Series Connections
Steffen Borgwardt, Weston Grewe, Jon Lee
The investigation of combinatorial diameters of polyhedra is a classical topic in linear programming due to its connection with the possibility of an efficient pivot rule for the s…
An Algorithm for the Separation-Preserving Transition of Clusterings
Steffen Borgwardt, Felix Happach, Stetson Zirkelbach
The separability of clusters is one of the most desired properties in clustering. There is a wide range of settings in which different clusterings of the same data set appear. We a…
A Note on the Approximability of Deepest-Descent Circuit Steps
Steffen Borgwardt, Cornelius Brand, Andreas Emil Feldmann +1
Linear programs (LPs) can be solved by polynomially many moves along the circuit direction improving the objective the most, so-called deepest-descent steps (dd-steps). Computing t…
An implementation of steepest-descent augmentation for linear programs
Steffen Borgwardt, Charles Viss
Generalizing the simplex method, circuit augmentation schemes for linear programs follow circuit directions through the interior of the underlying polyhedron. Steepest-descent augm…
On the Computational Complexity of Finding a Sparse Wasserstein Barycenter
Steffen Borgwardt, Stephan Patterson
The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of probability measures with finite support. In this paper, we show that finding a ba…
A Column Generation Approach to the Discrete Barycenter Problem
Steffen Borgwardt, Stephan Patterson
The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of discrete probability measures. Although an exact barycenter is computable through…
Constructing Clustering Transformations
Steffen Borgwardt, Charles Viss
Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different clusterings of the same data set become relevant. For example, diff…
A Polyhedral Model for Enumeration and Optimization over the Set of Circuits
Steffen Borgwardt, Charles Viss
Circuits play a fundamental role in polyhedral theory and linear programming. For instance, circuits are used as step directions in various augmentation schemes for solving linear…
Improved Linear Programs for Discrete Barycenters
Steffen Borgwardt, Stephan Patterson
Discrete barycenters are the optimal solutions to mass transport problems for a set of discrete measures. Such transport problems arise in many applications of operations research…
Circuit Walks in Integral Polyhedra
Steffen Borgwardt, Charles Viss
Circuits play a fundamental role in the theory of linear programming due to their intimate connection to algorithms of combinatorial optimization and the efficiency of the simplex…
Power Diagram Detection with Applications to Information Elicitation
Steffen Borgwardt, Rafael M. Frongillo
Power diagrams, a type of weighted Voronoi diagrams, have many applications throughout operations research. We study the problem of power diagram detection: determining whether a g…
Good Clusterings Have Large Volume
S. Borgwardt, F. Happach
The clustering of a data set is one of the core tasks in data analytics. Many clustering algorithms exhibit a strong contrast between a favorable performance in practice and bad th…
An LP-based, Strongly-Polynomial 2-Approximation Algorithm for Sparse Wasserstein Barycenters
Steffen Borgwardt
Discrete Wasserstein barycenters correspond to optimal solutions of transportation problems for a set of probability measures with finite support. Discrete barycenters are measures…
On the Circuit Diameter Conjecture
Steffen Borgwardt, Tamon Stephen, Timothy Yusun
From the point of view of optimization, a critical issue is relating the combinatorial diameter of a polyhedron to its number of facets and dimension . In the seminal paper…
The Diameters of Network-flow Polytopes satisfy the Hirsch Conjecture
S. Borgwardt, J. A. De Loera, E. Finhold
We solve a problem in the combinatorics of polyhedra motivated by the network simplex method. We show that the Hirsch conjecture holds for the diameter of the graphs of all network…
Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data
Ethan Anderes, Steffen Borgwardt, Jacob Miller
Wasserstein barycenters correspond to optimal solutions of transportation problems for several marginals, and as such have a wide range of applications ranging from economics to st…
Efficient solutions for weight-balanced partitioning problems
Steffen Borgwardt, Shmuel Onn
We prove polynomial-time solvability of a large class of clustering problems where a weighted set of items has to be partitioned into clusters with respect to some balancing constr…
The Hierarchy of Circuit Diameters and Transportation Polytopes
Steffen Borgwardt, Jesús A. De Loera, Elisabeth Finhold +1
The study of the diameter of the graph of polyhedra is a classical problem in the theory of linear programming. While transportation polytopes are at the core of operations researc…
Edges vs Circuits: a Hierarchy of Diameters in Polyhedra
Steffen Borgwardt, Jesús A. De Loera, Elisabeth Finhold
The study of the graph diameter of polytopes is a classical open problem in polyhedral geometry and the theory of linear optimization. In this paper we continue the investigation i…