2 citations · 2 across the 10 of their papers we have counts for
9 papers · 1 filter
Matroid Contention Resolution with Concentration
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +1
Contention resolution schemes (CRS) are a fundamental and widely applied tool for rounding fractional solutions subject to combinatorial constraints. However, the known analyses of…
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +2
We study algorithmic matroid intersection coloring. Given matroids on a common ground set of elements, the goal is to partition into the fewest number of color clas…
A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
Meike Neuwohner, Olha Silina, Michael Zlatin
We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tr…
Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +1
This paper shows a polynomial-time algorithm that, given a general matroid and partition matroids , produces a coloring of the intersection $M = \cap…
The Online Submodular Assignment Problem
Daniel Hathcock, Billy Jin, Kalen Patton +2
Online resource allocation is a rich and varied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazi…
The Online Submodular Assignment Problem
Daniel Hathcock, Billy Jin, Kalen Patton +2
Online resource allocation is a rich and varied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazi…
Approximation Algorithms for Steiner Connectivity Augmentation
Daniel Hathcock, Michael Zlatin
We consider connectivity augmentation problems in the Steiner setting, where the goal is to augment the edge-connectivity between a specified subset of terminal nodes. In the Stein…
Approximation algorithms for Steiner Tree Augmentation Problems
R. Ravi, Weizhong Zhang, Michael Zlatin
In the Steiner Tree Augmentation Problem (STAP), we are given a graph , a set of terminals , and a Steiner tree spanning . The edges $L := E \setmi…
On Small-Depth Tree Augmentations
Ojas Parekh, R. Ravi, Michael Zlatin
We study the Weighted Tree Augmentation Problem for general link costs. We show that the integrality gap of the ODD-LP relaxation for the (weighted) Tree Augmentation Problem for a…