Global roundings of sequences

Benjamin Doerr

doi:10.1016/j.ipl.2004.07.002

Global roundings of sequences

Benjamin Doerr

Christian-Albrechts-University Kiel

Research output: Contribution to journal › Article › peer-review

Abstract

For a given sequence a = (a₁,..., a_n) of numbers, a global rounding is an integer sequence b = (b₁,..., b_n) such that the rounding error | ∑_i∈I(a_i-b _i) | is less than one in all intervals I ⊆ {1,..., n}. We give a simple characterization of the set of global roundings of a. This allows to compute optimal roundings in time O(n log n) and generate a global rounding uniformly at random in linear time under a non-degeneracy assumption and in time O(n log n) in the general case.

Original language	English
Pages (from-to)	113-116
Number of pages	4
Journal	Information Processing Letters
Volume	92
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2004.07.002
Publication status	Published - 15 Nov 2004
Externally published	Yes

Keywords

Combinatorial problems
Discrepancy
Integral approximation
Rounding

Access to Document

10.1016/j.ipl.2004.07.002

Cite this

@article{d25b1b1714b44822a8a373a88f8cab6b,

title = "Global roundings of sequences",

abstract = "For a given sequence a = (a1,..., an) of numbers, a global rounding is an integer sequence b = (b1,..., bn) such that the rounding error | ∑i∈I(ai-b i) | is less than one in all intervals I ⊆ \{1,..., n\}. We give a simple characterization of the set of global roundings of a. This allows to compute optimal roundings in time O(n log n) and generate a global rounding uniformly at random in linear time under a non-degeneracy assumption and in time O(n log n) in the general case.",

keywords = "Combinatorial problems, Discrepancy, Integral approximation, Rounding",

author = "Benjamin Doerr",

year = "2004",

month = nov,

day = "15",

doi = "10.1016/j.ipl.2004.07.002",

language = "English",

volume = "92",

pages = "113--116",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "3",

}

TY - JOUR

T1 - Global roundings of sequences

AU - Doerr, Benjamin

PY - 2004/11/15

Y1 - 2004/11/15

N2 - For a given sequence a = (a1,..., an) of numbers, a global rounding is an integer sequence b = (b1,..., bn) such that the rounding error | ∑i∈I(ai-b i) | is less than one in all intervals I ⊆ {1,..., n}. We give a simple characterization of the set of global roundings of a. This allows to compute optimal roundings in time O(n log n) and generate a global rounding uniformly at random in linear time under a non-degeneracy assumption and in time O(n log n) in the general case.

AB - For a given sequence a = (a1,..., an) of numbers, a global rounding is an integer sequence b = (b1,..., bn) such that the rounding error | ∑i∈I(ai-b i) | is less than one in all intervals I ⊆ {1,..., n}. We give a simple characterization of the set of global roundings of a. This allows to compute optimal roundings in time O(n log n) and generate a global rounding uniformly at random in linear time under a non-degeneracy assumption and in time O(n log n) in the general case.

KW - Combinatorial problems

KW - Discrepancy

KW - Integral approximation

KW - Rounding

UR - https://www.scopus.com/pages/publications/4744344878

U2 - 10.1016/j.ipl.2004.07.002

DO - 10.1016/j.ipl.2004.07.002

M3 - Article

AN - SCOPUS:4744344878

SN - 0020-0190

VL - 92

SP - 113

EP - 116

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Global roundings of sequences

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this