Nearest Multiple of a Vector
----------------------------

Are there fast algorithms for computing the multiple of 
a vector $b$ nearest to a vector $a$ in the 1-norm
and the max norm,

$\min_\lambda ||a-\lambda b||_1$,
$\min_\lambda ||a-\lambda b||_\inf$,

and the related problem

 $\min_\lambda max_i (a_i-\lambda b_i)$ ?

More precisely, I would like to know the corresponding 
active sets after $O(n)$ operations, if possible with a 
constant independent of the length of the data.

------------------------------------------------
Improvements to the contents of this page are welcome.
Please write me to neum@cma.univie.ac.at

Arnold Neumaier

------------------------------------------------
1. Peter Spellucci (spellucci@mathematik.tu-darmstadt.de) wrote
(but I couldn't translate this into an O(n) algorithm; if you, reader, 
can, please write me!):

your functions to be minimized are convex piecewise linear in one
variable \lambda. It suffices therefore the check the "kinks" 
(points of nondifferentiability) and this is O(n).

-------------------------------------------------
2. David Stewart (dstewart@math.uiowa.edu) wrote:

I can give an O(n\log n) method for the first problem:

for i = 1, 2, ..., n
  if b_i < 0 then
    a_i <- -a_i; b_i <- -b_i;
  end if
end for

(Ignore any i where b_i = 0.)

Sort the indices so that
	a_1/b_1\le a_2/b_2\le a_3/b_3\le ....\le a_n/b_n
(This is the O(n\log n) part.)

[find sign change of derivative]
sum1 <- \sum_{i=1}^n b_i
sum2 <- 0
for i = 1, 2, ..., n
  sum1 <- sum1 - b_i
  sum2 <- sum2 + b_i
  if sum1 < sum2 then
    optimum lambda <- a_i/b_i & exit loop
  end if
end for

----------------------------------------------
3. Daniel Zwick (zwick@double-star.com) wrote:

Those are certainly interesting problems.  
The minmax problem can be converted to 2-variable linear programs of 
the form
  Minimize y 
  Subject to y >= +/-(a_i + b_i x) ( i = 1 to n)
and solved by, say, the simplex method. However this would not be O(n). The others can also be converted to 2-varible linear programs.
    
On the other hand, they are equivalent to Halfspace Intersection, 
which is equivalent to Convex Hull, and this can be solved in 
O(n log h) time, where in this case h would be the number of vertices 
visited in solving the problem. There is a O(n) algorithm for this 
problem, by N. Megiddo, but I don't know anyone who has actually 
programmed it.  He proved that a linear program in two variables 
(actually, fixed dimension) and n constraints can be solved in 
optimal O(n) time.  There is a nice discussion of this with an 
indication of how it might be programmed in the book 
"Computational Geometry" by Preparata and Shamos (around p.292).  

The book of Preparata and Shamos doesn't contain the latest references 
on these type of problems.  There are papers that reduce the constant 
(subexponential bounds in the dimension d), and some papers on 
randomized algorithms for the same lp problem.  Unfortunately I don't 
have all of these references, but I would start by searching for 
papers by G=E4rtner, Welzl, Sharir, and Clarkson (and combinations 
thereof). Dyer has (at least) two papers on Megiddo's technique, the one
mentioned in Preparata and Shamos, SIAM J Comp 13 (1984), p. 33 and 
another one in SIAM J Comp 15 (1986), p. 725.  It's still Megiddo's 
O(n) algorithm but with minor improvements.

-------------------------------------------------
I followed this up. The O(n) method is based on an O(n) method for
finding the median, but checking on median algorithms, I noticed that
apparently no one is using O(n) median algorithms since the factor 
hidden in the Landau symbol seems to be so large that simpler 
O(n log n) median methods are faster in practice, even for large n.
This suggests that for practical purposes, one should be content in 
the above problems with O(n log n) algorithms. 

But it also suggests that there is further scope for research.
Along the way I found some interesting WWW pages and references
that might be useful:

http://graphics.lcs.mit.edu/~seth/geomlib/geomlib.html
[lp, Mike Hohmeyer's C implementation of Raimund Seidel's O(d! n) time
linear programming algorithm]

http://www.geom.umn.edu/software/cglist/lp.html
Low-dimensional linear programming codes
[_expected_ O(n)]

http://cm.bell-labs.com/cm/cs/who/clarkson/lp2.html
K. L.Clarkson. Las Vegas algorithms for linear and integer programming
when the dimension is small. Journal of the ACM, 42(2):488--499, 1995.
[with source code that is _expected_ O(n)]

http://www.maths.mu.oz.au/~worms/digest/lp.html
[Recently, Gil Kalai and (independently) Matousek, Sharir, and Welzl 
have developed a randomized "subexponential" pivot rule for the 
simplex method.]

http://www.cs.sunysb.edu/~algorith/implement/linprog/implement.shtml

http://www.inf.ethz.ch/personal/gaertner/
Bernd Gärtner

http://www.inf.fu-berlin.de/inst/theo/mitarbeiter/welzl.html
Emo Welzl

D. Eppstein,
Dynamic three-dimensional linear programming,
ORSA J. Comput. 4 (1992), 360--368.
 
R. Seidel,
Small-dimensional linear programming and convex hulls made easy,
Discrete Comput. Geom. 6 (1991), 423--434.