Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling

[2608.15159] Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Data Structures and Algorithms arXiv:2608.15159 (cs) [Submitted on 15 Aug 2026] Title: Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling Authors: Sander Borst , Golnoosh Shahkarami , Rohit Vaish View a PDF of the paper titled Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling, by Sander Borst and 2 other authors View PDF HTML (experimental) Abstract: We study interval scheduling from the perspective of fair allocation. There are $m$ identical machines and a set of intervals, each specified by a start time, an end time, and a nonnegative weight. A schedule assigns a subset of the intervals to the machines so that no two intervals on the same machine overlap, and the goal is to maximize the total weight of scheduled intervals. Viewing machines as agents and intervals as goods, we require the schedule to be envy-free up to one item (EF1), and we measure efficiency against the offline optimum without fairness. In the offline setting, we give an algorithm that computes an EF1 schedule whose loss is at most a factor of $3/2$ in the unweighted regime, and we prove lower bounds of $\frac{3m-2}{2m-1}$, approaching $3/2$, in both the unweighted and the unit-length weighted regimes, so the price of fairness is $3/2$ in the limit. In the online setting, intervals arrive in nondecreasing order of start times; an arriving interval must be accepted or rejected, rejections are irrevocable, and an accepted interval may be revoked, and lost, at any time before it ends. For the unweighted regime we present Greedy-Balanced, a simple algorithm that maintains EF1 at every point in time and is $(2-\tfrac{1}{m})$-competitive against the offline optimum without fairness, and we prove a matching lower bound for every deterministic algorithm; the optimal deterministic fair competitive ratio is thus exactly $2-\tfrac{1}{m}$. Experiments on real-world benchmark instances show that Greedy-Balanced performs well beyond its worst-case guarantee, with an observed ratio never exceeding $1.306$. Subjects: Data Structures and Algorithms (cs.DS) ; Computer Science and Game Theory (cs.GT) Cite as: arXiv:2608.15159 [cs.DS] (or arXiv:2608.15159v1 [cs.DS] for this version) https://doi.org/10.48550/arXiv.2608.15159 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Golnoosh Shahkarami [ view email ] [v1] Sat, 15 Aug 2026 10:24:38 UTC (76 KB) Full-text links: Access Paper: View a PDF of the paper titled Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling, by Sander Borst and 2 other authors View PDF HTML (experimental) TeX Source view license Current browse context: cs.DS < prev | next > new | recent | 2026-08 Change to browse by: cs cs.GT References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Fair Division Meets Scheduling: Approximately Envy-Free Interval Scheduling#611107
• Simultaneous Envy and Equitability Guarantees#1084340
• Sequential Pricing Mechanisms for Surplus Division#924902
• Sequential Pricing Mechanisms for Surplus Division#920668
• Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching#1131153