On the Computational Complexity of Linear Discrepancy

DOI10.4230/LIPICS.ESA.2020.69MaRDI QIDQ5874541zbMATH OpenOpenAlexFDO

Authors Lily Qiao Li, Aleksandar Nikolov

Publication date 7 February 2023

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

zbMATH Keywords

NP-hardnessroundingdiscrepancy theorylinear discrepancy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Irregularities of distribution, discrepancy (11K38)

Recommendations

• scientific article; zbMATH DE number 1947049
• Typical rounding problems
• Roundings respecting hard constraints
• STACS 2005

Cites work

• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 741007 (Why is no real title available?)
• scientific article; zbMATH DE number 863495 (Why is no real title available?)
• A logarithmic additive integrality gap for bin packing
• An optimal convex hull algorithm in any fixed dimension
• Better scalable algorithms for broadcast scheduling
• Complexity of automaton identification from given data
• Computing largest empty circles with location constraints
• Discrepancy of set-systems and matrices
• Factorization norms and hereditary discrepancy
• Geometric discrepancy. An illustrated guide
• Tight hardness results for minimizing discrepancy
• Tighter bounds for the discrepancy of boxes and polytopes
• Tusnády's problem, the transference principle, and non-uniform QMC sampling
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• (2+)-Sat is NP-hard

Cited in

(7)

• STACS 2005
• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• scientific article; zbMATH DE number 1947049 (Why is no real title available?)
• Linear discrepancy is _2-hard to approximate
• Typical rounding problems
• Roundings respecting hard constraints
• scientific article; zbMATH DE number 1754592 (Why is no real title available?)

This page was built for publication: On the Computational Complexity of Linear Discrepancy

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