Name
Abstract | ||
|---|---|---|
We consider the 1-median problem in R^d with the Chebyshev norm: given n points with non-negative weights, find a point that minimizes the sum of the weighted distances to the given points. We propose a combinatorial algorithm for this problem by reformulating it as a fractional b-matching problem. This graph-theoretical problem can be solved by a min-cost-flow algorithm. Moreover, we show that there is a 1-median, which is half-integral, provided that the points have integral coordinates. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.orl.2010.07.002 | Oper. Res. Lett. |
Keywords | Field | DocType |
chebyshev norm,fractional b-matching problem,n point,1-median problem,graph-theoretical problem,weighted distance,combinatorial algorithm,fractional b -matching,non-negative weight,facility location,min-cost-flow algorithm | Chebyshev polynomials,Combinatorics,Mathematical optimization,Combinatorial algorithms,Matching (graph theory),Combinatorial optimization,Facility location problem,Chebyshev filter,Rational function,1-center problem,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 5 | Operations Research Letters |
Citations | PageRank | References |
1 | 0.38 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Hatzl | 1 | 59 | 7.96 |
| Andreas Karrenbauer | 2 | 133 | 20.21 |