Discrepancy methods improve rounding while meeting hard constraints

Approximation algorithms via discrepancy with hard constraints

Data Structures and Algorithms

Summary

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.

What this means in practice

  • For network engineers: Design routing schemes in grids and tori that strictly meet constraints while minimizing cost increases.
  • For scheduling coordinators: Schedule multicast communications to respect hard resource constraints without raising operational costs.

Authors

Mikhail Cherniavskii, Andrey Kupavskii, Stanislav Moiseev, Alexander Shekhovtsov

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.