Showing 2025Show all
3 papers · 1 filter
cs.GT2025
The Landscape of Almost Equitable Allocations
Hadi Hosseini, Vishwa Prakash HV, Aditi Sethia +1
Equitability is a fundamental notion in fair division which requires that all agents derive equal value from their allocated bundles. We study, for general (possibly non-monotone)…
cs.GT2025
Best-of-Both-Worlds Guarantees with Fairer Endings
Telikepalli Kavitha, Surya Panchapakesan, Rohit Vaish +2
We study best-of-both-worlds guarantees for the fair division of indivisible goods. Prior work has shown that under additive valuations, there always exists a randomized allocation…
cs.DS2025
Robust-Sorting and Applications to Ulam-Median
Ragesh Jaiswal, Amit Kumar, Jatin Yadav
Sorting is one of the most basic primitives in many algorithms and data analysis tasks. Comparison-based sorting algorithms, like quick-sort and merge-sort, are known to be optimal…