Browse Prior Art Database

A LINEAR-TIME ALGORITHM FOR THE WEIGHTED MEDIAN PROBLEM

IP.com Disclosure Number: IPCOM000128169D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 8 page(s) / 27K

Publishing Venue

Software Patent Institute

Related People

Chaya Bleich: AUTHOR [+4]

Abstract

We present a linear-time algorithm for the weighted median problem, which arises as a subproblem in certain multivariate optimization problems, including linear L, approximation. The algorithm, which is stated recursively, is based on the well known linear-time algorithm for the standard median problem. Compu-tational experience with the linear median algorithms for both the unweighted and weighted cases is described. April 22, 1983 *This work was supported in part by National Science Foundation Grant MCS-81-01924 and in part by the Office of Naval Research Graduate Fellowship Program.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 18% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A LINEAR-TIME ALGORITHM FOR THE WEIGHTED MEDIAN PROBLEM

Chaya Bleich and Michael L. Overton

April 1983

Report No. A Linear-Time Algorithm for the Weighted Median Problem*

Chaya Bleich and Michael L. Overton

Computer Science Department Courant Institute of Afathematical Sciences New York University

ABSTRACT

We present a linear-time algorithm for the weighted median problem, which arises as a subproblem in certain multivariate optimization problems, including linear L, approximation. The algorithm, which is stated recursively, is based on the well known linear-time algorithm for the standard median problem. Compu-tational experience with the linear median algorithms for both the unweighted and weighted cases is described.

April 22, 1983

*This work was supported in part by National Science Foundation Grant MCS-81-01924 and in part by the Office of Naval Research Graduate Fellowship Program. >A Linear-Time Algorithm for the Weighted Medi Ilan Problem*

Chaya Bleich and Michael L. Overton

Computer Science Department Courant Institute of Mathematical Sciences New York University

1. Introduction The weighted median problem is the following: given n unordered real numbers X1, - - - and associated positive real weights wl, W., solve:

(Equation Omitted)

If the weights are all one, the problem reduces to that of finding a median of n numbers, for which a linear-time algorithm is well known (see The problem (1) arises as a subproblem - namely the line search - in methods for solving the multidimensional linear L, problem 12], 131, 141):

8 min

(Equation Omitted)

and a method 171 for minimizing a sum of Euclidean norms:

(Equation Omitted)

Northwestern University Page 1 Dec 31, 1983

Page 2 of 8

A LINEAR-TIME ALGORITHM FOR THE WEIGHTED MEDIAN PROBLEM

These line searches are generally implemented by a partial sorting technique, using either heap-sort or quicksort. The problem (1) is easily solved by such a method. To see this let us first derive optimality conditions. It is easily seen that the left and right derivatives of f are respec- tively given by:

(Equation Omitted)

(Equation Omitted)

Since f is convex and piecewise linear, a necessary and sufficient condition for x to solve

(Equation Omitted)

or equivalently,

(Equation Omitted)

*This work was supported in part by National Science Foundation Grant MCS41-01924 and in part by the Office of Naval Research Graduate Fellowship Program.

>-2-

where

(Equation Omitted)

Clearly, a solution will always be given by one of the points xj, although there may in some cases be a continuum of solutions in the interval between two of the points. An algorithm based on partial heapsorting therefore is described as follows:

1. Let

(Equation Omitted)

in a heap.

3. While 8 < f do extract the smallest of the remaining from the heap, say xj, and readjust the heap. 8

(Equation Omitted)

It is clear that the algorithm terminates with xi an optimal solution....