Papers for

scheduling coordinators

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Discrepancy methods improve rounding while meeting hard constraints

Approximation algorithms via discrepancy with hard constraints

Abstract: In this paper, we present a discrepancy-based approach to cost-preserving rounding under hard constraints. Starting from a feasible fractional solution, our rounding procedure preserves the designated hard constraints, never increases the linear objective, and bounds the error in the remaining constraints by the discrepancy of a suitable column-difference matrix. Our second discrepancy-theoretic result bounds the discrepancy of a matrix in terms of a novel column parameter, called mountain distance. This notion captures ordered structural features of a matrix which are invisible to the classical Beck--Fiala and Komlós column-norm parameters. We show a variety of applications of these two results. In particular, we obtain new results for min-cost unsplittable flows, bounded-turn routing in grids and tori, rainbow prefix hypergraph decomposition, and $2$-multicast scheduling.

Mon 12 OctData Structures and Algorithms
The gist
Sometimes, computers need to turn a smooth, fractional answer into a strict yes-or-no one without breaking important rules or making costs go up. This paper introduces a new way to do that rounding, using a math tool called discrepancy to control how much the solution can stray. The authors also discovered a new property called 'mountain distance' that helps better measure this discrepancy in certain structured problems. Their approach works well for various tasks like routing data, scheduling, and network flows while keeping key conditions exactly met.
Open → 2610.16079v1

Polynomial algorithms achieve fair and envy-free item allocations

Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees

Abstract: We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) is a strengthening of the maximin share (MMS). A polynomial-time algorithm is known to guarantee a $2n/(3n-1)$ approximation of APS, but without an accompanying envy-based guarantee. Separately, allocations simultaneously satisfying minimum EFX share (MXS) and envy-freeness up to one less-preferred good (EFL), and subsequently the stronger requirement of residual maximin share (RMMS) together with EFL, have been shown to exist. However, the known constructions do not provide pseudopolynomial-time guarantees. We develop algorithms that combine these share-based and envy-based fairness requirements. First, for every $\varepsilon \in (0,1)$, we give an algorithm that computes an allocation satisfying exact EFL, $(1-\varepsilon)$-MXS, and $2n/(3n-1)$-APS. Its running time is polynomial in the binary input length and $1/\varepsilon$. Thus, we match the previously established polynomial-time APS approximation while simultaneously guaranteeing exact EFL and an arbitrarily close approximation to MXS. Second, we provide a pseudopolynomial-time algorithm that simultaneously guarantees exact MXS, exact EFL, and $2n/(3n-1)$-APS. Third, for every fixed number of agents, we obtain a pseudopolynomial-time algorithm that simultaneously achieves exact RMMS and exact EFL. Finally, we establish that computing a numerical threshold between MXS and RMMS is weakly NP-hard, even for additive valuations. This identifies a computational barrier to extending our polynomial-time approach to exact MXS through independently computed residual-valid share thresholds.

Sun 11 OctComputer Science and Game Theory
The gist
Dividing items fairly among people is hard when the items cannot be split. The paper finds ways to assign items so that each person feels they have a fair share and does not envy others, using efficient algorithms. The authors improved previous methods by combining two fairness ideas—sharing fairly and avoiding envy—and ensuring their algorithms run in reasonable time. They also show a complexity limit for some fairness measures, explaining why certain exact solutions are hard to find.
Open → 2610.15437v1