Dynamic algorithms for submodular matching
From MaRDI portal
Cites work
- A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
- A framework for dynamic matching in weighted graphs
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Combinatorial auctions with decreasing marginal utilities
- Deterministic fully dynamic data structures for vertex cover and matching
- Dynamic algorithms for matroid submodular maximization
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster scaling algorithms for general graph matching problems
- Fully dynamic (1+ e)-approximate matchings
- Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time
- Fully dynamic maximal matching in O( n) update time
- Fully dynamic maximal matching in constant update time
- Fully Dynamic Maximal Matching in O (log n) Update Time
- Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- scientific article; zbMATH DE number 1256640 (Why is no real title available?)
- scientific article; zbMATH DE number 1304326 (Why is no real title available?)
- scientific article; zbMATH DE number 6866348 (Why is no real title available?)
- scientific article; zbMATH DE number 7788452 (Why is no real title available?)
- Improved approximation guarantees for weighted matching in the semi-streaming model
- Improved approximations for k-exchange systems (extended abstract)
- Improved streaming algorithms for weighted matching, via unweighted matching
- Linear-time approximation for maximum weight matching
- Maintaining a large matching and a small vertex cover
- Maintaining approximate maximum weighted matching in fully dynamic graphs
- Matching theory
- Matroid matching: the power of local search
- Matroid prophet inequalities
- Matroid Secretary Problems
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing Non-monotone Submodular Functions
- Modern dynamic data structures (invited talk)
- Multi-budgeted matchings and matroid intersection via dependent rounding
- Navigating central path with electrical flows: from flows to matchings, and back
- Non-monotone submodular maximization under matroid and knapsack constraints
- On the complexity of dynamic submodular maximization
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Optimal approximation for the submodular welfare problem in the value oracle model
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Randomized primal-dual analysis of RANKING for online bipartite matching
- Simple deterministic algorithms for fully dynamic maximal matching
- Simplified and space-optimal semi-streaming (2+)-approximate matching
- Submodular maximization meets streaming: matchings, matroids, and more
- Submodular maximization over multiple matroids via generalized exchange properties
- Submodular maximization with nearly optimal approximation, adaptivity and query complexity
- Weighted matching in the semi-streaming model
This page was built for publication: Dynamic algorithms for submodular matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346449)
