The slack constant of Theorem B
DefinitionShortBroadcastDom_Supplement_deltaAdistributed-algorithmsdominating-setgraph-theorylinear-programmingp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a rational put . The slack constant of Theorem B is
For example and . It is the slack that threshold rounding achieves after the transformation of Theorem B.
Formalization Note is Int.fract (2a), and " is an integer" is Int.fract (2a) = 0.
Definition code
import Mathlib
namespace ShortBroadcastDom.Supplement
open Classical in
/-- **The slack constant `δ_a` of Theorem B.** For `a ≥ 1` with `θ = 2a − ⌊2a⌋`,
`δ_a = 1 / (2a(2a + 1)²)` if `2a` is an integer, and
`δ_a = min{(1 − θ)/(a(a + 1)), θ/(⌊2a⌋ + 1)}` otherwise.
Amiri, Siebertz, Wawrzyniak, *Paying for Fractional Error* (arXiv:2611.02057, sha256 prefix
f4dc98d2), Theorem B, §1.1, p.2 (PDF 5): "threshold rounding has slack at least
δa = 1/(2a(2a + 1)²) if 2a is an integer, δa = min{(1 − θ)/(a(a + 1)), θ/(⌊2a⌋ + 1)} otherwise,
where θ = 2a − ⌊2a⌋."
**Formalization Note** `θ = Int.fract (2a) = 2a − ⌊2a⌋`, and "`2a` is an integer" is
`Int.fract (2a) = 0`. Hand check: `a = 1` gives `1/18` (`= 1/(d b²)` with `d = 2`, `b = 3`, as in
the proof on p.48); `a = 5/4` gives `θ = 1/2` and `min{(1/2)/(45/16), (1/2)/3} = 1/6`. -/
noncomputable def deltaA (a : ℝ) : ℝ :=
if Int.fract (2 * a) = 0 then 1 / (2 * a * (2 * a + 1) ^ 2)
else min ((1 - Int.fract (2 * a)) / (a * (a + 1))) (Int.fract (2 * a) / ((⌊2 * a⌋ : ℝ) + 1))
end ShortBroadcastDom.Supplement
Source
Amiri, Siebertz, Wawrzyniak, Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts (arXiv:2611.02057, sha256 f4dc98d2cf73d74a105e5b0e61c4b72d15ae82b3f202490e2e4ecf864b40646a), §1.1, p.2 (PDF p.5), Theorem B