CS Paper Radar

A Deadline-Driven Algorithm for Polyamorous Scheduling

Arjun Maneesh Agarwal

cs.DS ·submitted 2026-09-09 11:36 UTC · v3

Abstract

In Polyamorous Scheduling Problem, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time between consecutive occurrences of the same edge. This NP-hard problem generalises Bamboo Garden Trimming and is motivated by the need to find schedules of pairwise meetings in a complex social group. We present a $4 G^*$ algorithm for Polyamorous Scheduling, improving the previously known bound of $3 + \sqrt{5} \approx 5.236$. Our algorithm is inspired by the Deadline-Driven Heuristic which is optimal for Bamboo Garden Trimming (BGT).

Comment
There is an error in section 2, right after the proof of Lemma 1. We claimed s <= 2(1/g_e - 1/g_f). This doesn't hold. Furthermore, the algorithm presented doesn't lead to constant bounded heat

Closest papers

Nearest neighbours by meaning across the whole index.

Minimizing the makespan in job shop scheduling under conflict graph constraints

cs.DM math.OC ·2026-09-03 ·Nour Elhouda Tellache, Abdenour Azerine
similarity 0.57
Abstract

We study the job shop scheduling problem with a conflict graph, in which adjacent jobs cannot be processed simultaneously on different machines, with the objective of minimizing the makespan. We establish a polynomial equivalence with a resource-constrained job shop problem having unit-capacity resources and binary resource requirements The problem is strongly NP-hard even on two machines with unit-time operations. For this setting, we derive an optimal-makespan formula and a linear-time algorithm when the conflict graph is a cluster graph, given the clique partition. We also develop a polynomial-time $4/3$-approximation algorithm for arbitrary conflict graphs on two machines when each job has exactly two unit-time operations. For the general problem, we propose four mixed-integer linear formulations, lower bounds, and a genetic algorithm with active, non-delay, and hybrid decoding procedures. Computational experiments on instances derived from the Lawrence and Taillard benchmarks and on randomly generated generalized job shop instances evaluate the proposed methods and show that the genetic algorithm generally improves on constructive heuristics.

0.34

Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation

cs.DS ·2026-09-28 ·Shreyas Ghildiyal, Muralidhara V N
similarity 0.57
Abstract

In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constraints this is interval graph coloring and is solvable in polynomial time through greedy approaches. We study a variant in which every used machine must remain idle during a contiguous \emph{break} of prescribed length $x$ somewhere in the scheduling horizon. We show that this additional constraint makes the problem hard, except when $x\le1$. First, for every fixed $x\ge2$, deciding whether $k$ machines suffice for the assignment of a given set of jobs is NP-complete, even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard. Second, for $x=1$, we give a polynomial-time algorithm that solves the problem exactly. Finally, we give a deterministic polynomial-time algorithm that, on every feasible instance, outputs a schedule using at most $\OPT+1$ machines, where $\OPT$ is the true minimum. Unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm guarantees $\OPT$ machines for any fixed $x\ge2$, so the additive guarantee of one is best possible.

0.07

Improved Approximations for Coflow Scheduling via Iterated Rounding and Stable Matchings

cs.DS ·2026-10-12 ·Mikhail Cherniavskii, Arseni Fedorovich, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev +2 more
similarity 0.56
Abstract

We study Coflow Scheduling, introduced by Chowdhury, Zhong, and Stoica (2014). We give deterministic polynomial-time algorithms achieving a $2.77$-approximation without release dates and a $3.17$-approximation with integer release dates. These improve the $3.42$ and $4.36$ guarantees of Rohwedder and Schnaars (2025). Our approach combines two ideas: (1) a novel iterated rounding scheme, and (2) Galvin's list edge coloring method, which is based on the Gale--Shapley stable matching algorithm.

0.25

Makespan Bounds for Synchronous Pebble Motion on Graphs

cs.DS ·2026-11-04 ·Lucy McManamon, Jingjin Yu
theory similarity 0.54
Abstract

We study the largest minimum makespan of labeled pebble motion on graphs under a model that permits synchronous pebble movement. While classical pebble motion on graphs allows only one pebble to move at a time, our model permits any number of pebbles to move to an adjacent vertex, provided that no two pebbles collide. At full occupancy every vertex is assigned a pebble and a legal round consists of disjoint cycle rotations. We prove a series of makespan bounds for this problem on graphs with varying structure and pebble density. For cycles with a chord, we extend a known quadratic bound at span two to every fixed span. For random cubic graphs, we convert permutation routing via matchings into legal schedules in two ways, applying cycle-cover batching at full occupancy and disjoint vacancy-delivery paths below full occupancy. For simple 3-connected planar cubic graphs, we prove a tight linear class maximum at every pebble count. We extend the results to increasing degree, common-neighbor conditions, and vertex connectivity. The results describe how graph connectivity, cycle structure, expansion, planarity, and occupancy affect worst-case routing time.

0.33

Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times

cs.CC cs.DMmath.CO ·2026-09-23 ·Zhi-Long Chen, Nicholas G. Hall
theory similarity 0.53
Abstract · 38 pages, 2 figures, 5 tables

We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize total weighted tardiness. Although closely related equal-processing-time problems admit polynomial-time algorithms, the complexity of this problem has remained open in the literature since 2010. We prove that its decision version is strongly NP-complete, even when every job can meet its due date if processed immediately upon release. The reduction is from unweighted MAX-CUT and uses a quadratic number of jobs with polynomially bounded numerical data. Its main ingredient is a constructive normalization theorem that converts every sufficiently inexpensive feasible schedule into a binary choice for each graph vertex; after normalization, total weighted tardiness equals a constant minus a scaled cut value. We also give a deterministic polynomial-time phase-grid assignment algorithm for the shifted objective $Φ=F+p\sum_jw_j$, where $F$ is total weighted tardiness. The algorithm enumerates at most $N$ release-date residues modulo $p$, solves one minimum-cost assignment problem for each residue, and returns the best phase-grid schedule. It runs in $O(N^5)$ arithmetic operations and achieves the tight ratio $3/2-1/(2N)$ for this algorithm. Because the added term $p\sum_jw_j$ is independent of how the jobs are scheduled, the shifted and original objectives have exactly the same optimal schedules. However, the approximation guarantee applies to the shifted objective; for the original objective, the analysis provides an additive bound. Thus, the paper both resolves the long-standing complexity question and provides a complementary worst-case guarantee for the phase-grid assignment algorithm.

0.21

The Power of Migration on Identical Machines is Two

cs.DS cs.DM ·2026-11-09 ·Nicole Megow, Bart Zondervan
similarity 0.52
Abstract

We study the power of migration in preemptive scheduling on identical parallel machines with time windows. If an instance admits a migratory schedule on $m$ machines, how many machines are needed to schedule it without migration? Kalyanasundaram and Pruhs (2001) showed that $6m-5$ machines suffice and gave a polynomial-time construction using $12m-5$ machines, whereas $2m-1$ machines may be necessary. We close this gap, which has been open for more than 25 years: $2m-1$ machines always suffice, and a corresponding non-migratory schedule can be computed in strongly polynomial time. Our proof has two main technical ingredients. First, we introduce supercanonical schedules and prove that the conflict graph of every such schedule on $m$ machines is $(2m-1)$-colorable. The key property is that whenever a job pauses, the jobs running alongside it just before and just after the pause separate the jobs processed entirely during the pause from the rest of the conflict graph. We use these separators and Kempe exchanges to compute a coloring in polynomial time. Second, we construct a supercanonical schedule with polynomially many processing blocks by shrinking job windows as far as possible while preserving feasibility and solving a min-cost flow problem.

0.10

Online Bin Packing with Dispatch Deadlines

cs.DS ·2026-11-05 ·Pei-Lin Chiang, Wing-Kai Hon, Kazuo Iwama, Li-Tzu Yang
published similarity 0.52
Abstract · 16 pages, 1 figure. Full version of a paper to appear in the 37th International Symposium on Algorithms and Computation (ISAAC 2026)

We study a generalization of online bin packing by introducing dispatch deadlines. Items arrive over time in an online fashion. Each item has an arrival time, a size in $(0,1]$, and a deadline, all of which are revealed only when the item arrives. The algorithm must immediately and irrevocably assign the item to a unit-capacity bin that has not yet been dispatched. Each bin must be dispatched no later than the earliest deadline of the items assigned to it, and once it is dispatched, it cannot be used for future items. The goal is to minimize the number of bins used. Applications arise naturally in logistics. Additionally, the offline version of this problem has appeared under several names, including the clique partition problem in weighted interval graphs and the BinSchedule problem. This problem is also a special case of online bin packing with conflicts and is closely related to online bin packing models with delay costs. We study the competitive ratios of several classical online bin packing algorithms when applied to this problem, and show that a similar hierarchy of competitive ratios carries over. Our main technical results are that the competitive ratio of First-Fit is exactly $16/7 \approx 2.28571$, and that no deterministic online algorithm has a competitive ratio less than $11/5 = 2.2$, showing that First-Fit is quite close to best possible. In addition, Next-Fit and Worst-Fit have competitive ratio exactly $3$, and every algorithm in the Any-Fit class has competitive ratio between $16/7$ and $3$.

0.36

Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs

cs.DM math.CO ·2026-10-01 ·Gautam K. Das, Kamal Santra
similarity 0.52
Abstract

An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $ρ_e^o(G)=α(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.

0.07