Cover Image

Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Halpern, Daniel, Psomas, Alexandros, Verma, Paritosh, Xie, Daniel
Format:	Preprint
Published:	2025
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

Algorithmic Persuasion with Evidence
by: Hoefer, Martin, et al.
Published: (2020)

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

On Interim Envy-Free Allocation Lotteries
by: Caragiannis, Ioannis, et al.
Published: (2021)

Weighted Envy Freeness With Bounded Subsidies
by: Elmalem, Noga Klein, et al.
Published: (2024)

Envy-freeness in 3D Hedonic Games
by: McKay, Michael, et al.
Published: (2022)

Envy-Free School Redistricting Between Two Groups
by: Shibatani, Daisuke, et al.
Published: (2026)

Minimum Envy Graphical House Allocation Beyond Identical Valuations
by: Inamdar, Tanmay, et al.
Published: (2026)

Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
by: Kawase, Sota, et al.
Published: (2024)

Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations
by: Bilò, Vittorio, et al.
Published: (2025)

Welfare Approximation in Additively Separable Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

Online Job Assignment
by: Ekbatani, Farbod, et al.
Published: (2025)

Online Block Packing
by: Eliezer, Ariel Ben, et al.
Published: (2025)

Online Matroid Embeddings
by: Cristi, Andrés, et al.
Published: (2024)

Online Resource Allocation with Cancellations
by: Ekbatani, Farbod, et al.
Published: (2022)

Stochastic Online Correlated Selection
by: Chen, Ziyun, et al.
Published: (2024)

Stability in Online Coalition Formation
by: Bullinger, Martin, et al.
Published: (2023)

Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
by: Bullinger, Martin, et al.
Published: (2025)

Online Combinatorial Allocation with Interdependent Values
by: Feldman, Michal, et al.
Published: (2025)

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

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

Universal Online Contention Resolution with Preselected Order
by: Zhao, Junyao
Published: (2025)

Robustness of Online Inventory Balancing to Inventory Shocks
by: Feng, Yiding, et al.
Published: (2025)

Risk-Sensitive Online Selection with Bounded Adaptivity
by: Nekouyan, Hossein, et al.
Published: (2025)

Threshold Testing and Semi-Online Prophet Inequalities
by: Hoefer, Martin, et al.
Published: (2023)

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)

Online Nash Welfare Maximization Without Predictions
by: Huang, Zhiyi, et al.
Published: (2022)

Fair and Efficient Allocations Without Obvious Manipulations
by: Psomas, Alexandros, et al.
Published: (2022)

Posted Price Mechanisms for Online Allocation with Diseconomies of Scale
by: Jazi, Hossein Nekouyan, et al.
Published: (2025)

Selfish, Local and Online Scheduling via Vector Fitting
by: Kashaev, Danish
Published: (2025)

Static Pricing for Online Selection Problem and its Variants
by: Sun, Bo, et al.
Published: (2024)

Addressing Bias in Online Selection with Limited Budget of Comparisons
by: Benomar, Ziyad, et al.
Published: (2023)

Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach
by: Livanos, Vasilis, et al.
Published: (2024)

Repeated Descent: A Framework for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2026)

Threshold Policies with Tight Guarantees for Online Selection with Convex Costs
by: Tan, Xiaoqi, et al.
Published: (2023)

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

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
by: Borst, Sander, et al.
Published: (2026)

Online Coalition Formation under Random Arrival or Coalition Dissolution
by: Bullinger, Martin, et al.
Published: (2023)

A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2025)