4 papers
Approximation Algorithms for Matroidal Prerequisite Systems
Robert P. Streit, Vijay K. Garg
Optimal selections in a decision process are often constrained by prerequisites. However, such prerequisites can encode functional rather than literal dependencies, so a required d…
Constrained Cuts, Flows, and Lattice-Linearity
Robert Streit, Vijay K. Garg
In a capacitated directed graph, it is known that the set of all min-cuts forms a distributive lattice [1], [2]. Here, we describe this lattice as a regular predicate whose forbidd…
The Polymatroid Representation of a Greedoid, and Associated Galois Connections
Robert P. Streit, Vijay K. Garg
A greedoid is a generalization of a matroid allowing for more flexible analyses and modeling of combinatorial optimization problems. However, these structures decimate many matroid…
Reducing Matroid Optimization to Basis Search
Robert Streit, Vijay K. Garg
Much energy has been devoted to developing a matroid's computational properties, yet parallel algorithm design for matroid optimization seems less understood. Specifically, the cur…