Cover Image

Approximate Bipartite $b$-Matching using Multiplicative Auction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Samineni, Bhargav, Ferdous, S M, Halappanavar, Mahantesh, Krishnamoorthy, Bala
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

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

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

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

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

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

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

Semi-Streaming Algorithms for Hypergraph Matching
by: Reinstädtler, Henrik, et al.
Published: (2025)

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

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
by: Azarmehr, Amir, et al.
Published: (2024)

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

A New Impossibility Result for Online Bipartite Matching Problems
by: Chierichetti, Flavio, et al.
Published: (2025)

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

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

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

When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching
by: Udwani, Rajan
Published: (2023)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

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

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

Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All
by: Panda, Atasi, et al.
Published: (2022)

Approximate Circular Pattern Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2022)

Approximate Cartesian Tree Matching with One Difference
by: Auvray, Bastien, et al.
Published: (2025)

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

Approximate Cartesian Tree Matching with Substitutions
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Engineering Hypergraph $b$-Matching Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Biclique Reconfiguration in Bipartite Graphs
by: Otachi, Yota, et al.
Published: (2026)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
by: Koenemann, Jochen, et al.
Published: (2021)

Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
by: Nanta, Jiratchaphat, et al.
Published: (2025)

Bipartite Exact Matching in P
by: Du, Yuefeng
Published: (2026)

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)

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

Approximate Circular Pattern Matching under Edit Distance
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Approximate Cartesian Tree Matching: an Approach Using Swaps
by: Auvray, Bastien, et al.
Published: (2023)

Time-Bucketed Balance Records: Bounded-Storage Ephemeral Tokens for Resource-Constrained Systems
by: Scovil, Shaun, et al.
Published: (2025)

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, et al.
Published: (2025)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

On the Complexity of Finding Approximate LCS of Multiple Strings
by: Hasibi, Hamed, et al.
Published: (2025)