On the Computational Complexity of Linear Discrepancy
From MaRDI portal
Recommendations
Cites work
- (2+)-Sat is NP-hard
- 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
- 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?)
- 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
Cited in
(7)- Typical rounding problems
- Linear discrepancy is _2-hard to approximate
- Roundings respecting hard constraints
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- scientific article; zbMATH DE number 1947049 (Why is no real title available?)
- scientific article; zbMATH DE number 1754592 (Why is no real title available?)
- 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)
