Weighted median algorithms for \(L_ 1\) approximation

DOI10.1007/BF02017350zbMath0704.65044MaRDI QIDQ917229

Chaya Gurwitz

Publication date: 1990

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

line search; Computational experiments; \(L_ 1\) approximation; linear-time method; partial heapsort method; partial quicksort method; sorting methods; weighted median algorithms

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C05: Linear programming

65D99: Numerical approximation and computational geometry (primarily algorithms)

41A45: Approximation by arbitrary linear expressions

Related Items

A linear time algorithm for a matching problem on the circle, The Kantorovich metric for probability measures on the circle

Uses Software

• Find
• Algorithm 489

Cites Work

• Unnamed Item
• Unnamed Item
• A linear selection algorithm for sets of elements with weights
• Time bounds for selection
• A quadratically convergent method for minimizing a sum of euclidean norms
• A Stable Algorithm for Solving the Multifacility Location Problem Involving Euclidean Distances
• Least Absolute Deviations Curve-Fitting
• Expected time bounds for selection
• Minimization Techniques for Piecewise Differentiable Functions: The $l_1$ Solution to an Overdetermined Linear System
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• An Improved Algorithm for Discrete $l_1 $ Linear Approximation