From the 1 of 4 linked papers with an AI index.
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…
cs.DS2025
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…