ISSN:
1436-4646
Keywords:
Hit and run methods
;
redundancy
;
linear inequalities
;
coupon collector's problem
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The hit and run methods are probabilistic algorithms that can be used to detect necessary (nonredundant) constraints in systems of linear constraints. These methods construct random sequences of lines that pass through the feasible region. These lines intersect the boundary of the region at twohit-points, each identifying a necessary constraint. In order to study the statistical performance of such methods it is assumed that the probabilities of hitting particular constraints are the same for every iteration. An indication of the best case performance of these methods can be determined by minimizing, with respect to the hit probabilities, the expected value of the number of iterations required to detect all necessary constraints. We give a set of isolated strong local minimizers and prove that for two, three and four necessary constraints the set of local minimizers is the complete set of global minimizers. We conjecture that this is also the case for any number of necessary constraints. The results in this paper also apply to sampling problems (e.g., balls from an urn) and to the coupon collector's problem.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01586052
Permalink
