Fast Algorithms via Dynamic-Oracle Matroids

Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu

Type: Article

Publication Date: 2023-05-16

Citations: 2

DOI: https://doi.org/10.1145/3564246.3585219

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Fast Algorithms via Dynamic-Oracle Matroids	2023	Joakim Blikstad Sagnik Mukhopadhyay Danupon Nanongkai Ta-Wei Tu
+ PDF Chat	Accelerating Matroid Optimization through Fast Imprecise Oracles	2024	Franziska Eberle Felix Hommelsheim Alexander Lindermayr Zhenwei Liu Nicole Megow Jens Schlöter
+	Dynamic Set Cover: Improved Algorithms & Lower Bounds	2018	Amir Abboud Raghavendra Addanki Fabrizio Grandoni Debmalya Panigrahi Barna Saha
+	Dynamic Set Cover: Improved Algorithms & Lower Bounds	2018	Amir Abboud Raghavendra Addanki Fabrizio Grandoni Debmalya Panigrahi Barna Saha
+	Dynamic set cover: improved algorithms and lower bounds	2019	Amir Abboud Raghavendra Addanki Fabrizio Grandoni Debmalya Panigrahi Barna Saha
+	Matroids and the greedy algorithm	1971	Jack Edmonds
+ PDF Chat	Constant-Time Algorithms for Sparsity Matroids	2012	Hiro Ito Shin‐ichi Tanigawa Yuichi Yoshida
+	Query Lower Bounds for Matroid Intersection (Combinatorial Optimization and Discrete Algorithms)	2010	Nicholas J. A. Harvey
+	Changing Bases: Multistage Optimization for Matroids and Matchings	2014	Anupam Gupta Kunal Talwar Udi Wieder
+	Changing Bases: Multistage Optimization for Matroids and Matchings	2014	Anupam Gupta Kunal Talwar Udi Wieder
+	Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid	2023	Richard Santiago Ivan Sergeev Rico Zenklusen
+	Design of Dynamic Algorithms via Primal-Dual Method	2016	Sayan Bhattacharya Monika Henzinger Giuseppe F. Italiano
+	Matroid complexity and large inputs	2007	Dillon Mayhew
+	On Variants of the Matroid Secretary Problem	2011	Shayan Oveis Gharan Jan Vondrák
+	On Variants of the Matroid Secretary Problem	2011	Shayan Oveis Gharan Jan Vondrák
+	Design of Dynamic Algorithms via Primal-Dual Method	2016	Sayan Bhattacharya Monika Henzinger Giuseppe F. Italiano
+	New amortized cell-probe lower bounds for dynamic problems	2019	Sayan Bhattacharya Monika Henzinger Stefan Neumann
+	Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv	2022	Ce Jin Yinzhan Xu
+	Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid	2018	Niv Buchbinder Moran Feldman Mohit Garg
+ PDF Chat	Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs	2018	Itay Laish Shay Mozes

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Faster Matroid Partition Algorithms	2024	Tatsuya Terao

Works Cited by This (43)

Action	Title	Year	Authors
+	Edge-disjoint spanning trees and depth-first search	1976	Robert E. Tarjan
+	On a Class of Matroids Arising From Paths in Graphs	1972	John Mason
+	Transversals and matroid partition	1965	Jack Edmonds D.R. Fulkerso
+	Path Finding Methods for Linear Programming: Solving Linear Programs in &#x00D5;(vrank) Iterations and Faster Algorithms for Maximum Flow	2014	Yin Tat Lee Aaron Sidford
+ PDF Chat	Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back	2013	Aleksander Mądry
+	Fast Dynamic Weight Matchings in Convex Bipartite Graphs	2015	Quan Zu Miaomiao Zhang Bin Yu
+ PDF Chat	Fully-dynamic minimum spanning forest with improved worst-case update time	2017	Christian Wulff‐Nilsen
+ PDF Chat	A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization	2015	Yin Tat Lee Aaron Sidford Sam Chiu-wai Wong
+ PDF Chat	Computing Maximum Flow with Augmenting Electrical Flows	2016	Aleksander Mądry
+ PDF Chat	Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time	2017	Danupon Nanongkai Thatchaphol Saranurak Christian Wulff‐Nilsen