Cover Image

Beyond the Half-Approximation: Fair and Efficient Online Class Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Borst, Sander, Springer, Max
Format:	Preprint
Published:	2026
Subjects:	Computer Science and Game Theory Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fairness and Efficiency in Online Class Matching
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2024)

Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare
by: Zargari, Faraz, et al.
Published: (2025)

Fairness and Efficiency in Two-Sided Matching Markets
by: Jain, Pallavi, et al.
Published: (2025)

Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division
by: S, Ajaykrishnan E, et al.
Published: (2025)

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

Approximating Nash Social Welfare by Matching and Local Search
by: Garg, Jugal, et al.
Published: (2022)

Online Matching Meets Sampling Without Replacement
by: Huang, Zhiyi, et al.
Published: (2024)

Prophet Upper Bounds for Online Matching and Auctions
by: Soto, José, et al.
Published: (2024)

Truthful Matching with Online Items and Offline Agents
by: Feldman, Michal, et al.
Published: (2022)

Condorcet Dimension and Pareto Optimality for Matchings and Beyond
by: Kavitha, Telikepalli, et al.
Published: (2026)

Optimal Competitive Ratio of Two-sided Online Bipartite Matching
by: Tang, Zhihao Gavin
Published: (2026)

Revisiting Fair and Efficient Allocations for Bivalued Goods
by: Liu, Hui, et al.
Published: (2026)

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
by: Glitzner, Frederik, et al.
Published: (2025)

Edge-weighted Online Stochastic Matching Under Jaillet-Lu LP
by: Yan, Shuyi
Published: (2025)

Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
by: Pashkovich, Kanstantsin, et al.
Published: (2026)

Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
by: Yan, Shuyi
Published: (2022)

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
by: Peng, Bo, et al.
Published: (2025)

Bi-Criteria Metric Distortion
by: Banihashem, Kiarash, et al.
Published: (2024)

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
by: Andersen, Martin Jupakkal, et al.
Published: (2025)

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
by: Segev, Danny, et al.
Published: (2020)

Fair Repetitive Interval Scheduling
by: Heeger, Klaus, et al.
Published: (2024)

Conflict and Fairness in Resource Allocation
by: Bandopadhyay, Susobhan, et al.
Published: (2024)

Non-Monotonicity in Fair Division of Graphs
by: Hosseini, Hadi, et al.
Published: (2025)

Stable Matching with Interviews
by: Ashlagi, Itai, et al.
Published: (2025)

Robust Popular Matchings
by: Bullinger, Martin, et al.
Published: (2024)

Tradeoffs in Privacy, Welfare, and Fairness for Facility Location
by: Fish, Sara, et al.
Published: (2026)

Position Fair Mechanisms Allocating Indivisible Goods
by: Mahara, Ryoga, et al.
Published: (2024)

Fair Multi-agent Persuasion with Submodular Constraints
by: Bai, Yannan, et al.
Published: (2025)

Group Fair Matchings using Convex Cost Functions
by: Panda, Atasi, et al.
Published: (2025)

Stable Matching with Deviators and Conformists
by: Glitzner, Frederik, et al.
Published: (2026)

Group Fairness and Multi-criteria Optimization in School Assignment
by: A., Santhini K., et al.
Published: (2024)

Fair Rent Division: New Budget and Rent Constraints
by: Gangam, Rohith Reddy, et al.
Published: (2025)

Optimally Interpolating between Ex-Ante Fairness and Welfare
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

Matching with Nested and Bundled Pandora Boxes
by: Bowers, Robin, et al.
Published: (2024)

Stable Hypergraph Matching in Unimodular Hypergraphs
by: Biró, Péter, et al.
Published: (2025)

Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods
by: Kawase, Yasushi, et al.
Published: (2023)

Logarithmic Approximation for Road Pricing on Grids
by: Constantinescu, Andrei, et al.
Published: (2025)

Near-Feasible Stable Matchings: Incentives and Optimality
by: Glitzner, Frederik
Published: (2026)

A Minimax Perspective on Almost-Stable Matchings
by: Glitzner, Frederik, et al.
Published: (2026)

The Distortion of Prior-Independent b-Matching Mechanisms
by: Caragiannis, Ioannis, et al.
Published: (2026)