A linear time algorithm for computing minmax regret 1-median on a tree network (Q486974): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/s00453-013-9851-7 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2001915330 / rank | |||
Normal rank | |||
Revision as of 22:52, 19 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
