An algorithm for komlós conjecture matching Banaszczyk's bound

Nikhil Bansal, Daniel Dadush, Shashwat Garg

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
16 Downloads (Pure)

Abstract

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((tlog n) 1 / 2 ), matching the best known nonconstructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t 1 / 2 log n) bound. The result also extends to the more general Komlós setting and gives an algorithmic O(log 1 / 2 n) bound.

Original languageEnglish
Pages (from-to)534-553
Number of pages20
JournalSIAM Journal on Computing
Volume48
Issue number2
DOIs
Publication statusPublished - 30 Apr 2019

Fingerprint

Coloring
Colouring
Discrepancy
Set Systems
Efficient Algorithms

Keywords

  • Discrepancy
  • Random walk
  • Semidefinite programming
  • semidefinite programming
  • random walk
  • discrepancy

Cite this

Bansal, Nikhil ; Dadush, Daniel ; Garg, Shashwat. / An algorithm for komlós conjecture matching Banaszczyk's bound. In: SIAM Journal on Computing. 2019 ; Vol. 48, No. 2. pp. 534-553.
@article{bd2e1f9a3d2842c1991cb7ea5436a0ed,
title = "An algorithm for koml{\'o}s conjecture matching Banaszczyk's bound",
abstract = "We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((tlog n) 1 / 2 ), matching the best known nonconstructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t 1 / 2 log n) bound. The result also extends to the more general Koml{\'o}s setting and gives an algorithmic O(log 1 / 2 n) bound.",
keywords = "Discrepancy, Random walk, Semidefinite programming, semidefinite programming, random walk, discrepancy",
author = "Nikhil Bansal and Daniel Dadush and Shashwat Garg",
year = "2019",
month = "4",
day = "30",
doi = "10.1137/17M1126795",
language = "English",
volume = "48",
pages = "534--553",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics (SIAM)",
number = "2",

}

An algorithm for komlós conjecture matching Banaszczyk's bound. / Bansal, Nikhil; Dadush, Daniel; Garg, Shashwat.

In: SIAM Journal on Computing, Vol. 48, No. 2, 30.04.2019, p. 534-553.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - An algorithm for komlós conjecture matching Banaszczyk's bound

AU - Bansal, Nikhil

AU - Dadush, Daniel

AU - Garg, Shashwat

PY - 2019/4/30

Y1 - 2019/4/30

N2 - We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((tlog n) 1 / 2 ), matching the best known nonconstructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t 1 / 2 log n) bound. The result also extends to the more general Komlós setting and gives an algorithmic O(log 1 / 2 n) bound.

AB - We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((tlog n) 1 / 2 ), matching the best known nonconstructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t 1 / 2 log n) bound. The result also extends to the more general Komlós setting and gives an algorithmic O(log 1 / 2 n) bound.

KW - Discrepancy

KW - Random walk

KW - Semidefinite programming

KW - semidefinite programming

KW - random walk

KW - discrepancy

UR - http://www.scopus.com/inward/record.url?scp=85065485172&partnerID=8YFLogxK

U2 - 10.1137/17M1126795

DO - 10.1137/17M1126795

M3 - Article

AN - SCOPUS:85065485172

VL - 48

SP - 534

EP - 553

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 2

ER -