6 papers
A Canceling Heuristic for the Directed Traveling Salesman Problem
Steffen Borgwardt, Zachary Sorenson
The Traveling Salesman Problem (TSP) is one of the classic and hard problems in combinatorial optimization. We develop a new heuristic that uses a connection between Minimum Cost F…
On Circuit Imbalance and 0/1 Circuits for Coloring and Forest Problems
Steffen Borgwardt, Nicholas Crawford, Sean Kafer +2
Circuits are fundamental objects in linear programming and oriented matroid theory, representing the elementary difference vectors of a polyhedron. A recent concept introduced by D…
Improved Decomposition Bounds for Partition Polytopes and Odd-Covers
Steffen Borgwardt, Zdeněk Dvořák, Bryce Frederickson +2
The assignments of a set of items into clusters of prescribed sizes can be encoded as the vertices of the partition polytope . W…
Evacuation Planning on Time-Expanded Networks with Integrated Wildfire Information
Steffen Borgwardt, Nicholas Crawford, Drew Horton +2
We study the problem of evacuation planning for natural disasters, focusing on wildfire evacuations. By creating pre-planned evacuation routes that can be updated based on real-tim…
Combinatorics of generalized parking-function polytopes
Margaret M. Bayer, Steffen Borgwardt, Teressa Chambers +8
For , a -parking function is defined to be a sequence of positive integers whose nondecreasing rearra…
On Combinatorial Network Flows Algorithms and Circuit Augmentation for Pseudoflows
Steffen Borgwardt, Angela Morrison
There is a wealth of combinatorial algorithms for classical min-cost flow problems and their simpler variants like max flow or shortest path problems. It is well-known that many of…