NDLI: Sampling with Removal in LP-type Problems

Please wait, while we are loading the content...

Counting and Enumerating Crossing-free Geometric Graphs

A Framework for Computing the Greedy Spanner

There are Plane Spanners of Maximum Degree 4

New and Improved Spanning Ratios for Yao Graphs

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures

Progressive Geometric Algorithms

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp

The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems

Design of 3D printed mathematical art

Embeddability in the 3-sphere is decidable

The Connect-The-Dots Family of Puzzles: The Video

LiveCG: an Interactive Visualization Environment for Computational Geometry

Trajectory Grouping Structure: the Video

Visualizing hyperbolic Voronoi diagrams

Animation of an Algorithm for Drawing Graphs in 3D

Visualization of Floater and Gotsman's Morphing Algorithm

Geometric kth Shortest Paths: the Applet

Polytope Offsets and Straight Skeletons in 3D

Optimal Geometric Flows via Dual Programs

Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons

A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

Outerstring graphs are χ-bounded

Improved bounds for the conflict-free chromatic art gallery problem

Linear transformation distance for bichromatic matchings

Delaunay triangulations with disconnected realization spaces

Eliminating Tverberg Points, I. An Analogue of the Whitney Trick

Higher Dimensional Cheeger Inequalities

Incidences between points and lines in R4: Extended Abstract

On triple intersections of three families of unit circles

Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage

Smallest enclosing ball for probabilistic data

Peeling Potatoes Near-Optimally in Near-Linear Time

On the Complexity of Randomly Weighted Voronoi Diagrams

A Census of Plane Graphs with Polyline Edges

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited

Using Convex Relaxations for Efficiently and Privately Releasing Marginals

Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Better embeddings for planar Earth-Mover Distance over sparse sets

Higher-Quality Tetrahedral Mesh Generation for Domains with Small Angles by Constrained Delaunay Refinement

On the reconstruction of convex sets from random normal measurements

Intersection of paraboloids and application to Minkowski-type problems

Efficient Random-Walk Methods for Approximating Polytope Volume

The Persistent Homology of Distance Functions under Random Projection

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Computing Topological Persistence for Simplicial Maps

Induced Matchings of Barcodes and the Algebraic Stability of Persistence

Towards Expressive 3D Modeling: new challenges for geometric computing

Computing the Fréchet distance with shortcuts is NP-hard

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Light spanners for Snowflake Metrics

Continuously Flattening Polyhedra Using Straight Skeletons

Two-Point L1 Shortest Path Queries in the Plane

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Free Edge Lengths in Plane Graphs

Weight Balancing on Boundaries and Skeletons

Separation by Convex Pseudo-Circles

Euclidean Steiner Shallow-Light Trees

Measuring Distance between Reeb Graphs

Stochastic Convergence of Persistence Landscapes and Silhouettes

The Morse Theory of Čech and Delaunay Filtrations

Gromov-Hausdorff Approximation of Filament Structure Using Reeb-type Graph

Metric Embedding, Hyperbolic Space, and Social Networks

Sampling with Removal in LP-type Problems

Liftings and stresses for planar periodic frameworks

The Opaque Square

The JS-graphs of Join and Split Trees

Distinct distances on algebraic curves in the plane

Lower bounds on geometric Ramsey functions

Curves in Rd intersecting every hyperplane at most d + 1 times

Sampling with Removal in LP-type Problems

Content Provider	ACM Digital Library
Author	Gärtner, Bernd
Abstract	Random sampling is an important tool in optimization subject to finitely or infinitely many constraints. Here we are interested in obtaining solutions of low cost that violate only few constraints. Under convexity or similar favorable conditions, and assuming fixed dimension, one can indeed derive combinatorial bounds on the expected number (or probability mass) of constraints violated by the optimal solution subject to a (small) random sample of constraints. The cost of the sample solution, however, cannot be bounded combinatorially. Suppose that for a fixed integer k, we locally minimize the cost by removing k constraints from the sample. Can we still guarantee (good) bounds on the number or mass of violated constraints? This question was asked and partially answered in the framework of chance-constrained optimization [1]. Here we study the question in the completely combinatorial setting of LP-type problems that allows a unified treatment of many different optimization problems. Given a nondegenerate LP-type problem of combinatorial dimension Δ, we prove that sampling with removal of the best k constraints induces an LP-type problem of combinatorial dimension O(Δk+1), and this bound is tight in the worst case. It follows that through this kind of removal, the expected number of violated constraints blows up by a factor of at most O(Δk); for relevant sample sizes, however, a matching lower bound for the blowup factor is not implied. At the same time, our results show that further improvements require new tools that go beyond combinatorial dimension.
Starting Page	511
Ending Page	518
Page Count	8
File Format	PDF
ISBN	9781450325943
DOI	10.1145/2582112.2582121
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-08
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in