On the Computational Complexity of Linear Discrepancy

DOI10.4230/LIPICS.ESA.2020.69OpenAlexW3082438618MaRDI QIDQ5874541FDOQ5874541

Authors: Lily Qiao Li, Aleksandar Nikolov 

Publication date: 7 February 2023

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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+\varepsilon)\)-Sat is NP-hard

Cited In (7)

• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• Title not available (Why is that?)
• Linear discrepancy is \(\Pi_2\)-hard to approximate
• Typical rounding problems
• Roundings respecting hard constraints
• Title not available (Why is that?)
• STACS 2005

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)