A linear time algorithm for computing minmax regret 1-median on a tree network (Q486974): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 00:25, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear time algorithm for computing minmax regret 1-median on a tree network |
scientific article |
Statements
A linear time algorithm for computing minmax regret 1-median on a tree network (English)
0 references
19 January 2015
0 references
The facility location problem is to minimize the communication or transportation costs. The cost function is formulated as the sum of distances from the nearest facility weighted by the weights of the vertices. The previous most efficient algorithm for finding minimum regret 1-median in a tree network with nonnegative vertex weights takes \(O(n\log n)\) time. The author's algorithm takes linear time, i.e. \(O(n)\).
0 references
facility location
0 references
robust median
0 references
uncertain weights
0 references
minmax regret
0 references
