Showing 2021Show all
2 papers · 1 filter
cs.DS2021
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection
Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
Submodular function minimization (SFM) and matroid intersection are fundamental discrete optimization problems with applications in many fields. It is well known that both of these…
cs.DS2021
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
Yu Chen, Sanjeev Khanna, Ansh Nagda
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Bencz…