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.