Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Doerr, Benjamin

dblp



BibTeX cite key*:

DoerrTCS2007

Title

Title*:

Roundings respecting hard constraints

Journal

Journal Title*:

Theory of Computing Systems

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:


Publisher's
Address:

Berlin, Germany

ISSN:

1432-4350

Vol, No, pp, Date

Volume*:

40

Number:

4

Publishing Date:

2007

Pages*:

467-483

Number of
VG Pages:


Page Start:

467

Page End:

483

Sequence Number:


DOI:

10.1007/s00224-006-1318-7

Note, Abstract, ©

Note:


(LaTeX) Abstract:

 A problem arising in integer linear programming is transforming a solution of a linear system to an integer one that is "close." The customary model for investigating such problems is, given a matrix A and a [0,1]-valued vector x, finding a binary vector y such that ||A(x - y)||∞, the maximum violation of the constraints, is small. Randomized rounding and the algorithm of Beck and Fiala are ways to compute such solutions y, whereas linear discrepancy is a lower bound measure. In many applications one is looking for roundings that, in addition to being close to the original solution, satisfy some constraints without violation. The objective of this paper is to investigate such problems in a unified way. To this aim, we extend the notion of linear discrepancy to include such hard cardinality constraints. We extend the algorithm of Beck and Fiala to cope with this setting. If the constraints contain disjoint sets of variables, the rounding error increases by only a factor of two. We also show how to generate and derandomize randomized roundings respecting disjoint cardinality constraints. However, we also provide some examples showing that additional hard constraints may seriously increase the linear discrepancy. In particular, we show that the c-color linear discrepancy of a totally unimodular matrix can be as high as Ω(log c).

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{DoerrTCS2007,
AUTHOR = {Doerr, Benjamin},
TITLE = {Roundings respecting hard constraints},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2007},
NUMBER = {4},
VOLUME = {40},
PAGES = {467--483},
ADDRESS = {Berlin, Germany},
ISBN = {1432-4350},
DOI = {10.1007/s00224-006-1318-7},
}


Entry last modified by Süntje Böttcher, 06/09/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Anja Becker
Created
02/08/2008 02:07:58 PM
Revisions
2.
1.
0.

Editor(s)
Süntje Böttcher
Anja Becker
Anja Becker

Edit Dates
09.06.2008 22:38:08
25.02.2008 08:47:07
08.02.2008 14:10:33