scientific article; zbMATH DE number 1528185

Publication date: 12 November 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

sampling optimization linear programming Markov chains textbook computer graphics probabilistic algorithms computational geometry circuit complexity mathematical finance derandomization searching machine learning communication complexity Voronoi diagrams complexity theory pseudorandomness algorithm design discrepancy method

Mathematics Subject Classification ID

Numerical methods (including Monte Carlo methods) (91G60) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Learning and adaptive systems in artificial intelligence (68T05) Linear programming (90C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Complexity and performance of numerical algorithms (65Y20)

Related Items

An efficient $k$ nearest neighbors searching algorithm for a query line., Optimal approximations made easy, Zero-sum subsequences in bounded-sum $\{-1,1\}$-sequences, The structure and number of global roundings of a graph, Typical rounding problems, A strong lower bound for approximate nearest neighbor searching, Lower bounds for intersection searching and fractional cascading in higher dimension, Constructive Discrepancy Minimization by Walking on the Edges, Recent progress on combinatorics and algorithms for low discrepancy roundings, Covering many or few points with unit disks, Improved sparse Fourier approximation results: Faster implementations and stronger guarantees, Cuttings for disks and axis-aligned rectangles in three-space, A crossing lemma for Jordan curves, Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond, Powers of Hamilton cycles of high discrepancy are unavoidable, Almost envy-freeness for groups: improved bounds via discrepancy theory, Generalized ham-sandwich cuts, On generalizations of network design problems with degree bounds, Approximately uniform online checkpointing with bounded memory, Bisecting and $D$-secting families for set systems, A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs, Mean isoperimetry with control on outliers: exact and approximation algorithms, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, Geometric characterization of Weyl's discrepancy norm in terms of its $n$-dimensional unit balls, Quantum discrepancy: a non-commutative version of combinatorial discrepancy, The power of online thinning in reducing discrepancy, Optimal jittered sampling for two points in the unit square, Computer-aided proof of Erdős discrepancy properties, Improved distributed degree splitting and edge coloring, Near-optimal coresets of kernel density estimates, Hardness of discrepancy computation and $\varepsilon$-net verification in high dimension, Cubature formulas, discrepancy, and nonlinear approximation, Range minima queries with respect to a random permutation, and approximate range counting, Uniformly inserting points on square grid, Randomness of the square root of 2 and the giant leap. I, Sampling scattered data with Bernstein polynomials: stochastic and deterministic error estimates, Constructive Discrepancy Minimization for Convex Sets, Computing generalized ham-sandwich cuts, On the largest empty axis-parallel box amidst $n$ points, Piercing quasi-rectangles-on a problem of Danzer and Rogers, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Maximizing coverage while ensuring fairness: a tale of conflicting objectives, Toric algebra of hypergraphs, On simplifying dot maps., Four deviations suffice for rank 1 matrices, Covering numbers, dyadic chaining and discrepancy, Online Inserting Points Uniformly on the Sphere, A survey of average case complexity for linear multivariate problems, The range of a simple random walk on $\mathbb{Z}$: an elementary combinatorial approach, The Kadison-Singer problem in discrepancy theory., Zero-sum subsequences in bounded-sum $\{-r,s\}$-sequences, Fibonacci sets and symmetrization in discrepancy theory, Intersections of hypergraphs, The cycle discrepancy of three-regular graphs, Approximate range searching in higher dimension, Zero-sum squares in bounded discrepancy $\{-1,1\}$-matrices, Learning Complexity vs Communication Complexity, Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions, The Littlewood-Gowers problem, Discrepancy of line segments for general lattice checkerboards, Positive-definite functions, exponential sums and the greedy algorithm: a curious phenomenon, The convexification effect of Minkowski summation, Computing the coarseness with strips or boxes, $\varepsilon$-Mnets: Hitting geometric set systems with subsets, A generalization of magic squares with applications to digital halftoning, Computing hereditary convex structures, On the exponent of discrepancies, Combinatorial sublinear-time Fourier algorithms, Non-independent randomized rounding and coloring, Online uniformity of integer points on a line, Halton and Hammersley sequences in multivariate nonparametric regression, Approximate range searching: The absolute model, Deterministic discrepancy minimization, Computing the center region and its variants, Semidefinite optimization in discrepancy theory, Money creation process in a random redistribution model, Online uniformly inserting points on the sphere, Voronoi diagrams for a moderate-sized point-set in a simple polygon, Lower bounds for matrix factorization, The Geometry of Differential Privacy: The Small Database and Approximate Cases, Distributed noise-shaping quantization. I: Beta duals of finite frames and near-optimal quantization of random measurements, Octagonal symmetry in low-discrepancy β-manganese, Random sampling scattered data with multivariate Bernstein polynomials, Dynamically defined sequences with small discrepancy, Coloring geometric range spaces, Finding optimal volume subintervals with $ k$ points and calculating the star discrepancy are NP-hard problems, Small weak epsilon-nets, Discrepancy of high-dimensional permutations, Irregularities of distribution and geometry of planar convex sets, Subsampling in Smoothed Range Spaces, Deterministic and probabilistic discrepancies, Gaussian discrepancy: a probabilistic relaxation of vector balancing, Faster algorithms for growing prioritized disks and rectangles, Embedding Graphs Having Ore-Degree at Most Five, Upper and lower bounds for matrix discrepancy, Locally consistent constraint satisfaction problems, Data structures on event graphs, Poisson polyhedra in high dimensions, Optimal bounds for the predecessor problem and related problems, Uniformity of Point Samples in Metric Spaces Using Gap Ratio, Discrepancy in modular arithmetic progressions, A sharp discrepancy bound for jittered sampling, Lower bounds for the directional discrepancy with respect to an interval of rotations, A note on stabbing convex bodies with points, lines, and flats, The Phase Transition of Discrepancy in Random Hypergraphs, Unnamed Item, The discrepancy of random rectangular matrices, Irregularities of distribution for bounded sets and half‐spaces, On combinatorial properties of greedy Wasserstein minimization, Simplex Range Searching and Its Variants: A Review, TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES, Unnamed Item, An Improvement of the Beck–Fiala Theorem, One-bit sensing, discrepancy and Stolarsky's principle, On the discrepancy of random matrices with many columns, Approximating Tverberg points in linear time for any fixed dimension, An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound, On the Wasserstein distance between classical sequences and the Lebesgue measure, On splitting and splittable families, Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, Tight lower bounds for the size of epsilon-nets, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Cell-probe lower bounds for the partial match problem, Bregman Voronoi diagrams, On the discrepancy of jittered sampling, Towards uniform online spherical tessellations, Unnamed Item, The Communication Complexity of Distributed epsilon-Approximations, A discrepancy version of the Hajnal–Szemerédi theorem, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality, Tverberg theorems over discrete sets of points, Lower bounds for matrix factorization, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, Algorithmic Aspects of Combinatorial Discrepancy, Calculation of Discrepancy Measures and Applications, Weighted symmetrized centered discrepancy for uniform design