On the best case performance of hit and run methods for detecting necessary constraints

DOI10.1007/BF01586052zbMath0746.65053OpenAlexW2015181134MaRDI QIDQ1186280

Myron Hlynka, Richard J. Caron, J. Fred McDonald

Publication date: 28 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01586052

zbMATH Keywords

probabilistic algorithmsredundancylinear inequalitiescoupon collector's problemstatistical performancesampling problemsnumber of iterationssystems of linear constraintshit and run methods

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items

Optimal strategy of coupon subset collection when each package contains half of the coupons ⋮ Probabilistic algorithms for extreme point identification ⋮ On the best case performance of hit and run methods for detecting necessary constraints ⋮ Monte Carlo Algorithms for the Detection of Necessary Linear Matrix Inequality Constraints ⋮ Results and conjectures on the role of the uniform distribution in the coupon collector's problem with group drawings ⋮ Minimal representation of convex regions defined by analytic functions

Cites Work

• Unnamed Item
• Redundancy in mathematical programming. A state-of-the-art survey
• A new approach to the analysis of random methods for detecting necessary linear inequality constraints
• On the best case performance of hit and run methods for detecting necessary constraints
• Hit-and-run algorithms for the identification of nonredundant linear inequalities
• The coupon-collector problem revisited — a survey of engineering problems and computational methods
• Shake-and-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra