Copertina

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Zheng, Da Wei, Henzinger, Monika
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Approximate Bipartite $b$-Matching using Multiplicative Auction
di: Samineni, Bhargav, et al.
Pubblicazione: (2024)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
di: Kwok, Shawxing
Pubblicazione: (2025)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
di: El-Hayek, Antoine, et al.
Pubblicazione: (2023)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
di: Henzinger, Monika, et al.
Pubblicazione: (2025)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
di: Chuzhoy, Julia, et al.
Pubblicazione: (2024)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
di: El-Hayek, Antoine, et al.
Pubblicazione: (2024)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
di: Hu, Hang, et al.
Pubblicazione: (2022)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
di: Henzinger, Monika, et al.
Pubblicazione: (2024)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
di: Zhao, Jingyang, et al.
Pubblicazione: (2025)

Efficient Kernelization Algorithm for Bipartite Graph Matching
di: Wu, Guang, et al.
Pubblicazione: (2024)

Improved Differentially Private Continual Observation Using Group Algebra
di: Henzinger, Monika, et al.
Pubblicazione: (2024)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
di: Soma, Tasuku, et al.
Pubblicazione: (2025)

A Fully-dynamic Approximation Algorithm for Maximum Weight b-Matchings in Graphs
di: Brandt-Tumescheit, Fabian, et al.
Pubblicazione: (2024)

Differentially Private Algorithms for Graphs Under Continual Observation
di: Fichtenberger, Hendrik, et al.
Pubblicazione: (2021)

Catalytic Tree Evaluation From Matching Vectors
di: Henzinger, Alexandra, et al.
Pubblicazione: (2026)

Concurrent Composition for Differentially Private Continual Mechanisms
di: Henzinger, Monika, et al.
Pubblicazione: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
di: Dempsey, Jordan, et al.
Pubblicazione: (2024)

Improved Approximation Algorithm for Maximum Balanced Biclique
di: Manurangsi, Pasin
Pubblicazione: (2026)

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
di: Kuo, Tung-Wei
Pubblicazione: (2024)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
di: D'Angelo, Gianlorenzo, et al.
Pubblicazione: (2025)

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
di: El-Hayek, Antoine, et al.
Pubblicazione: (2025)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
di: Assadi, Sepehr
Pubblicazione: (2023)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
di: Roditty, Liam, et al.
Pubblicazione: (2025)

Edge-Weighted Online Bipartite Matching
di: Fahrbach, Matthew, et al.
Pubblicazione: (2020)

Interval-Constrained Bipartite Matching over Time
di: Abels, Andreas, et al.
Pubblicazione: (2024)

Optimal Rounding for Two-Stage Bipartite Matching
di: Pollner, Tristan, et al.
Pubblicazione: (2025)

Efficient Contractions of Dynamic Graphs -- with Applications
di: Henzinger, Monika, et al.
Pubblicazione: (2025)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
di: la Tour, Max Dupré, et al.
Pubblicazione: (2024)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
di: Joseph, et al.
Pubblicazione: (2023)

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
di: Nägele, Martin, et al.
Pubblicazione: (2026)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
di: Blikstad, Joakim, et al.
Pubblicazione: (2024)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
di: Mahabadi, Sepideh, et al.
Pubblicazione: (2025)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
di: Davies-Peck, Peter
Pubblicazione: (2026)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
di: Ferdous, S M, et al.
Pubblicazione: (2023)

Improved Lower Bounds for Privacy under Continual Release
di: Aryanfard, Bardiya, et al.
Pubblicazione: (2025)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
di: Liu, Yang P.
Pubblicazione: (2024)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2023)

Degree-bounded Online Bipartite Matching: OCS vs. Ranking
di: Feng, Yilong, et al.
Pubblicazione: (2025)