5 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…
Parallel Algorithms for Equilevel Predicates
Vijay K. Garg, Robert P. Streit
We define a new class of predicates called equilevel predicates on a distributive lattice which eases the analysis of parallel algorithms. Many combinatorial problems such as the v…