Rounding Fractional Allocations via Pseudoforest Structures

17 concepts15 papers1 proposal

Many combinatorial optimization problems—such as scheduling jobs on unrelated machines or allocating indivisible goods to agents—can be naturally modeled as bipartite matching problems. To find approximate solutions efficiently, algorithms often solve a Linear Programming (LP) relaxation. The result is a fractional assignment, where an edge between a job node and a machine node carries a fractional weight $x_{ij} \in (0, 1)$.

The core challenge is rounding: how do we transform these fractions into integers (0 or 1) without overloading any machine or violating fairness guarantees? The key to doing this cleanly lies in the graph-theoretic structure of the LP's extreme points, which naturally form sparse graph structures known as pseudoforests.

Why Extreme Points Form Pseudoforests

An extreme point (or basic feasible solution) of a linear program is uniquely determined by a set of linearly independent tight constraints. In a standard bipartite allocation LP, constraints typically correspond to nodes: each job must be fully assigned ($\sum_j x_{ij} = 1$), and each machine has a capacity or load constraint.

If we construct a graph where edges represent fractional assignments ($0 < x_{ij} < 1$), the number of variables equals the number of edges $|E|$. Because these variables are uniquely determined by a system of tight node constraints, the number of edges $|E|$ cannot exceed the number of active node constraints. Since each constraint is tied to a vertex, the number of edges is bounded by the number of vertices:

$$|E| \le |V|$$

A graph where every connected component has at most as many edges as vertices is a pseudoforest. Each connected component is a pseudotree—a tree containing at most one cycle. As shown by José R. Correa et al. and José Correa et al., this structural property provides a powerful lever for rounding. Because the fractional graph is almost a tree, it contains very few cycles to resolve.

Resolving Cycles via Rotations and Shifts

The presence of a cycle in the fractional assignment graph means there is local ambiguity: a set of jobs can be shifted around a closed loop of machines without altering the total fractional assignment of any job.

To eliminate these cycles, algorithms use cycle cancellation or rotations. Consider an alternating cycle in the bipartite graph. We can modify the fractional values along the cycle by adding a small value $\epsilon$ to every alternating edge and subtracting $\epsilon$ from the remaining edges. Because every vertex in the cycle has exactly one incoming and one outgoing edge modified by the same $\epsilon$, the total load or assignment at each node remains perfectly invariant.

    (Machine A)      (Machine B)
       /    \           /    
  +\epsilon  -\epsilon +\epsilon
     /        \       /      
 (Job 1)      (Job 2)

By choosing $\epsilon$ such that at least one fractional edge drops to 0 or reaches 1, we remove that edge from the fractional graph without changing the node marginals.

Leah Epstein et al. introduced an early form of this cycle elimination technique to simplify assignment structures while preserving load properties across all $L_p$ norms. More recently, Yuda Feng et al. and Shi Li et al. utilized iterative rounding frameworks that repeatedly apply these rotations and path shifts to systematically strip cycles from configuration LPs. Because the shifts are carefully balanced, they maintain the marginal properties or tightly bound the cost increases of the continuous solution, as also demonstrated by Edin Husic et al. and Bo Li et al..

From Forests to Integral Assignments

Once all cycles within a pseudotree component are eliminated, the component simplifies into a true tree (or a forest across the whole graph). In a forest, the rounding problem becomes significantly easier due to the existence of leaf nodes (vertices with degree 1).

A leaf node in a bipartite assignment graph represents either a job connected to exactly one machine, or a machine connected to exactly one job.

  • If a job node is a leaf, its fractional weight on that single edge must be 1, meaning it is already integrally assigned.
  • If a machine node is a leaf, the remaining fractional job can be rounded up or down with minimal impact on that machine's total load.

By processing the tree from the leaves upward, algorithms can deterministically or dependently round the remaining fractional edges. For instance, Benjamin Birnbaum et al. use specialized subroutines to manage revenue loss during this forest transformation in budgeted allocations. Similarly, Samir Khuller et al. employ dependent rounding on these structures to ensure job assignments remain strictly within capacity bounds during machine activation.

Broad Applications

This structural rounding paradigm has proven remarkably versatile across two major domains:

Heterogeneous Scheduling

When scheduling complex workloads on unrelated processors—such as MapReduce jobs (Dimitris Fotakis et al.) or malleable tasks (Dimitris Fotakis et al.)—oriented pseudoforests allow designers to bound the makespan by ensuring each task is assigned either to a single primary machine or a tightly constrained subset of machines. Christos Kalaitzis et al. adapt this by partitioning machine capacities into ordered buckets before applying bipartite rounding.

Fair Division of Goods and Chores

In multi-agent resource allocation, ensuring fairness criteria like Maximin Share (MMS) or Any Price Share (APS) is notoriously difficult for indivisible items. By modeling the problem via pseudoforests, researchers can bound the extra load or utility an agent receives. Haris Aziz et al. use pseudoforest extreme points to bound the chore load assigned to asymmetric agents, while Chandra Chekuri et al. and Hannaneh Akrami et al. leverage cycle cancellation and payment graphs to guarantee high-quality approximate allocations for complex concave valuations and chores.

Key Foundational Work

All-Norm Approximation Algorithms (2002) — contributed 2 concept elements to this direction.
Improved Approximation Algorithms for Budgeted Allocations (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_pseudoforest_based_rounding_fac31e5e,
  title = {pseudoforest-based rounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pseudoforest-based-rounding/rdr_fac31e5e25d848bfa1f253a45386a7ef},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_pseudoforest_based_rounding_fac31e5e_v1,
  title = {pseudoforest-based rounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pseudoforest-based-rounding/rdr_fac31e5e25d848bfa1f253a45386a7ef/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake