Continuous Relaxations and Randomized Rounding for Combinatorial Optimization

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

Version 1 of 1214 papers225 conceptsfrozen 2026-10-04

Combinatorial optimization problems—from partitioning graphs to selecting the best set of sensors—are notoriously difficult because they require discrete "yes/no" decisions. In a graph with $N$ nodes, there are $2^N$ possible ways to assign them to groups, a search space that grows exponentially.

The core insight of this research direction is that we can solve these hard discrete problems by temporarily pretending they are continuous. By "lifting" discrete variables into a continuous space (a process called relaxation), we can use powerful tools like gradients and convex optimization to find a fractional solution. The final, crucial step is randomized rounding: a mathematical bridge that snaps these fractional values back to discrete integers while preserving the quality of the solution.

The Strategy: Relax, Optimize, and Sample

The most direct application of this idea is seen in the ROS (Relax-Optimize-and-Sample) framework. To solve the Max-$k$-Cut problem—partitioning a graph to maximize the weight of edges between different groups—Yong‐Qing Qiu, Zhi‐Quan Luo, and colleagues in ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-k-Cut Problems replace discrete group assignments with continuous probability distributions.

By optimizing these probabilities using a Graph Neural Network (GNN), they find a "soft" assignment for each node. The "Sample" phase then uses a probabilistic mechanism to convert these representations back into discrete partitions. The beauty of this approach is that the expected value of the discrete cut is theoretically equivalent to the continuous objective, ensuring that the GNN's progress isn't lost during discretization.

Lifting Submodular Functions

A significant portion of this field focuses on submodular maximization—optimizing functions that exhibit "diminishing returns." While these functions are defined over discrete sets, they can be extended into the continuous domain using "multilinear extensions" or "concave relaxations."

Alina Ene and Huy L. Nguyên demonstrate this in A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. They use a technique called Swap Rounding, which iteratively exchanges fractional components of a solution until it becomes discrete. This process ensures that the final set adheres to budget constraints (the "knapsack") while maintaining the approximation guarantees established in the continuous phase.

Similarly, Iasonas Nikolaou, Evimaria Terzi, and Stratis Ioannidis apply this to online settings in Online Two-Stage Submodular Maximization. Their algorithm, RAOCO, combines continuous relaxation with randomized rounding to select a "shortlist" of items before a user's specific utility is even known, achieving state-of-the-art performance by bridging the gap between fractional weights and discrete selections.

Advanced Rounding Mechanisms

Rounding is rarely as simple as "rounding to the nearest integer." Researchers have developed sophisticated mechanisms to handle complex constraints:

  • Pipage Rounding: Used in problems like team formation and caching, this technique moves fractional values toward the boundaries of a constraint polytope. T. Si-Salem and colleagues use it in Online Submodular Maximization via Online Convex Optimization to map fractional solutions back to discrete sets while satisfying matroid constraints.
  • Birkhoff-von Neumann Decomposition: In Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments, Steven Jecmen and Nihar B Shah use this to transform a matrix of assignment probabilities into a specific, valid reviewer-to-paper matching. This ensures that the final assignment respects reviewer capacities while maintaining the fairness properties of the original probability distribution.
  • Random Projections: For high-dimensional problems like haplotype assembly or MAP inference, researchers like Shreepriya Das in SDhaP use random projections to map continuous variables from Semidefinite Programming (SDP) relaxations back to discrete values.

Why It Works: The Proximity and Lossless Guarantees

The power of this research direction lies in the theoretical guarantees that ensure the "rounded" solution is close to the "optimal" continuous one.

In Differentiable extensions with rounding guarantees for combinatorial optimization over permutations, Yusu Wang introduces the Birkhoff Extension, which provides a "lossless" rounding guarantee. This means the objective value of the resulting discrete permutation is mathematically proven to be no worse than the value of the continuous relaxation.

For large-scale resource allocation, Thibaut Vidal and Daniel Gribel utilize a proximity theorem in Separable Convex Optimization with Nested Lower and Upper Constraints. They solve problems in the integer domain and map them back to continuous space, showing that the discrete and continuous optima remain tightly coupled even as the number of variables reaches the millions.

Applications Across Domains

This "relax-and-round" paradigm has become a standard template for solving intractable problems:

By treating discreteness as a final constraint rather than a starting point, these researchers have turned NP-hard combinatorial nightmares into manageable, continuous optimization problems.

Papers in this version

Showing 60 of 214 papers.

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_continuous_relaxations_and_randomized_ro_0f0c474d,
  title = {Continuous Relaxations and Randomized Rounding for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/continuous-relaxations-and-randomized-rounding-for-combinatorial-optimization/rdr_0f0c474da8ad425f8fbb3f8835fb7b6a},
  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_continuous_relaxations_and_randomized_ro_0f0c474d_v1,
  title = {Continuous Relaxations and Randomized Rounding for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/continuous-relaxations-and-randomized-rounding-for-combinatorial-optimization/rdr_0f0c474da8ad425f8fbb3f8835fb7b6a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}