Document Type
Report
Date
5-1996
Keywords
Median rule
Language
English
Disciplines
Computer Sciences
Description/Abstract
The solution of integer optimization problems by relaxation methods consists of three parts. First, the discrete problem is converted into a continuous optimization problem, which is generally more tractable. Second, the relaxed problem is solved efficiently, yielding a optimal solution in the continuous space. Finally, an assignment procedure is used to map this solution to a "suitable" discrete solution. One heuristic - we call it the relaxation heuristic - that often guides the choice and design of assignment algorithms is: "given a continuous optimal solution, the corresponding integer optimal solution is likely to be nearby" (with respect to some well defined metric). Intuitively, this heuristic is reasonable for objective functions that are, say, Lipschitz functions. For such functions, an assignment algorithm might map the continuous optimal solution to the nearest feasible solution in the discrete space, in the hope that the discrete solution will be optimal as well. In this paper, we consider properties of a particular assignment algorithm known as the median rule. Define a binary vector to be balanced when the numbers of its 1 's and 0's differ at most by one. The median rule used to assign n-dimensional real vectors to n-dimensional balanced binary vectors, may be loosely described as follows: map the ith component of a real vector to a 0 or 1, depending on whether that component is smaller or greater than the median value of the vector components. We address two aspects of the median rule. The first result is that given a real vector, the median rule produces the closest balanced binary vector, with respect to any Schur-convex distance criteria. This includes several Minkowski norms, entropy measures, gauge functions etc. In this sense, the median rule optimally implements the relaxation heuristic. The second result addresses the issue of relaxation error. Though the median rule produces the nearest balanced integer solution to a given real vector, it is possible that this solution is sub-optimal, and the actual optimal solution is located elsewhere. The difference between the actual optimal cost and the cost of the solution obtained by the median rule is called the relaxation error. We consider the optimization of real valued, parametrized, multivariable Lipschitz functions where domains are the set of balanced binary vectors. Varying the parameters over the range of their values, we obtain an ensemble of such problems. Each problem instance in the ensemble has an optimal real cost, an integer cost, and an associated relaxation error. We establish upper bounds on the probability that the relaxation error is greater than a given threshold t. In general, these bounds depend on the random model being considered. These results have an immediate bearing on the important graph bisection width problem, which involves the minimization of a certain semidefinite quadratic cost function over balanced binary domains. This important problem arises in a variety of areas including load balancing, [11,16], storage management [22], distributed directories [15], and VLSI design [10]. The results obtained indicate that the median rule in a certain precise sense, is an optimal assignment procedure for this problem. The rest of the paper is organized as follows: In section 3, we prove the shortest distance properties of the median rule. In section 4, we introduce the concept of relaxation error and the Lipschitz bisection problem. Upper bounds on the relaxation error are obtained in Section 5. A discussion on these results is given in Section 6.
Recommended Citation
Menon, Anil Ravindran; Mehrotra, Kishan; Mohan, Chilukuri K.; and Ranka, Sanjay, "Probabilistic Analysis of the Median Rule: Asymptotics and Applications" (1996). Electrical Engineering and Computer Science - Technical Reports. 146.
https://surface.syr.edu/eecs_techreports/146
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-96-02