From the 1 of 4 linked papers with an AI index.
4 papers
Reducing Matroid Optimization to Basis Search
Robert Streit, Vijay K. Garg
The paper introduces a reduction that converts binary matroid optimization into a basis search problem, enabling parallel algorithms that run in O(√n·log r) rounds while using only…
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…
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…
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…