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
• Approximation-friendly discrepancy rounding
• 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

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

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)