Optimal volume subintervals with k points and star discrepancy via integer programming

Eric Thiémard

Mathematical Methods of Operations Research, 2001, vol. 54, issue 1, 45 pages

Abstract: Given n points in the s-dimensional unit cube, we consider the problem of finding a subinterval of minimum or maximum volume that contains exactly k of the n points. We give integer programming formulations of these problems and techniques to tackle their resolution. These optimal volume problems are used in an algorithm to compute the star discrepancy of n points in the s-dimensional unit cube. We propose an ultimately convergent strategy that gradually reduces the size of an interval containing this value. Results of some star discrepancy experiments and an empirical study of the computation time of the method are presented. Copyright Springer-Verlag Berlin Heidelberg 2001

Keywords: Key words: Integer programming; computational geometry; star discrepancy. (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s001860100141 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:54:y:2001:i:1:p:21-45

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s001860100141

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().