Scheduling via Fractional Relaxation and Rounding

This direction is merged into another direction: linear programming relaxation. Its last version stays readable and citable here.

Version 1 of 155 papers61 conceptsfrozen 2026-10-04

Scheduling problems are fundamentally combinatorial. Whether assigning tasks to processors, charging electric vehicles, or ordering blockchain transactions, the core challenge is making discrete "yes or no" decisions: Should this job start at time $t$? Should it run on machine $A$ or $B$? These binary constraints make most realistic scheduling problems NP-hard, as seen in the work of Philippe Baptiste and Christoph Dürr, who demonstrated that even simple variations in job length can trigger computational intractability The Complexity of Mean Flow Time Scheduling Problems with Release Times.

To bypass this complexity, researchers have converged on a powerful meta-strategy: Fractional Relaxation and Rounding. Instead of solving the hard discrete problem directly, we allow jobs to be "split" across time and machines, solve this easier continuous version, and then carefully "glue" the pieces back together into a valid discrete schedule.

The Blueprint: Linear Programming Relaxations

The first step is to transform a discrete problem into a continuous one using Linear Programming (LP). In a relaxation, we replace binary constraints (where a variable $x$ must be 0 or 1) with interval constraints ($0 \le x \le 1$).

Different "blueprints" or formulations provide different levels of fidelity:

The resulting fractional solution is a "perfect" schedule in a world where jobs can be infinitely divided. It provides a mathematical lower bound on the best possible discrete schedule.

The Rounding Challenge: From Fractions to Integers

The core of this research area is the rounding scheme. If the LP says machine $A$ should do 0.7 of a job and machine $B$ should do 0.3, we must decide where the whole job actually goes. Simple rounding often fails because it violates capacity constraints or creates overlaps.

Randomized Rounding

A common approach is to treat the fractions as probabilities. Ariel Ben Eliezer applies this to blockchain transactions, showing that selecting tasks based on their fractional values can capture a significant portion of the total possible social welfare Online Block Packing. Similarly, Venkatesan Guruswami uses randomized rounding on configuration LPs to handle "constrained rejections," where some jobs must be left behind to optimize the rest Scheduling Problems with Constrained Rejections.

Shifting and Decrowding

Even after assigning a job to a machine, we must decide when it starts. Rounding often causes multiple jobs to "crowd" into the same time slot. Anupam Gupta and Amit Kumar pioneered techniques to "swap mass" between similar jobs and then shift the resulting schedule forward in time to resolve overlaps without violating release dates Scheduling with Outliers.

Christoph Damerius and Peter Kling refined this into a "decrowding" process, modeling the overlaps as paths in a bipartite graph and shifting workloads along those paths to ensure an integral schedule with provable performance bounds Scheduling with a Limited Testing Budget.

Applications: From Deep Learning to Smart Grids

This framework is not just theoretical; it is the engine behind modern system optimizations.

Why It Works: The Power of Global Context

The intuition behind the success of fractional relaxation is that the LP "sees" the entire problem at once. While a greedy algorithm might make a locally optimal choice that causes a disaster later, the fractional solution identifies a global distribution of work that respects all constraints. The rounding and shifting phases then act as a "local repair" mechanism, turning that global blueprint into a feasible, discrete reality.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scheduling_via_fractional_relaxation_and_8ad22eb8,
  title = {Scheduling via Fractional Relaxation and Rounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scheduling-via-fractional-relaxation-and-rounding/rdr_8ad22eb8f21c48e496ba5825eb25b7e6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_scheduling_via_fractional_relaxation_and_8ad22eb8_v1,
  title = {Scheduling via Fractional Relaxation and Rounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scheduling-via-fractional-relaxation-and-rounding/rdr_8ad22eb8f21c48e496ba5825eb25b7e6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}