Degree-Constrained Network Spanners with Nonconstant Delay

DOI10.1137/S0895480193251635MaRDI QIDQ4837654zbMATH OpenOpenAlexFDO

Authors Donald E. Knuth

Publication date 3 July 1995

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9504228

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Abstract: Given $n$ real numbers $0leq{x}_1,\mathrm{...},x_n<1$ and a permutation~$sigma$ of $1,\mathrm{...},n$, we can always find $xba{r}_1,\mathrm{...},xba{r}_{n}in0,1$ so that the partial sums $xba{r}_1+\mathrm{...}+xba{r}_k$ and $xba{r}_{sigma1}+\mathrm{...}+xba{r}_{sigmak}$ differ from the unrounded values $x_1+\mathrm{...}+x_k$ and $x_{sigma1}+\mathrm{...}+x_{sigmak}$ by at most $n/(n+1)$, for $1leqkleqn$. The latter bound is best possible. The proof uses an elementary argument about flows in a certain network, and leads to a simple algorithm that finds an optimum way to round.

Recommendations

• Global roundings of sequences
• scientific article; zbMATH DE number 1737508
• Rounding with multiplier methods: An efficient algorithm and applications in statistics
• Approximation and Online Algorithms

Cited in

(11)

• Rounding in symmetric matrices and undirected graphs
• Recent progress on combinatorics and algorithms for low discrepancy roundings
• Unbiased Matrix Rounding
• Roundings in partially ordered topological spaces
• scientific article; zbMATH DE number 1737508 (Why is no real title available?)
• The alternating stock size problem and the gasoline puzzle
• The alternating stock size problem and the gasoline puzzle
• Innocuous Double Rounding of Basic Arithmetic Operations
• Integer matrices with constraints on leading partial row and column sums
• Embedding multidimensional grids into optimal hypercubes
• Global roundings of sequences

This page was built for publication: Degree-Constrained Network Spanners with Nonconstant Delay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4837654)