1942:
2814:
1482:
2359:
1937:{\displaystyle {\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}y_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}y_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}d_{j}y_{ij}\leqslant u_{i}x_{i}{\text{ for all }}i=1\dots ,n\\&y_{ij}\geqslant 0{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}}
2809:{\displaystyle {\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}z_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}z_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1\dots ,n\\&z_{ij}\in \{0,1\}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}}
22:
151:, in which a single facility is to be placed, with the only optimization criterion being the minimization of the weighted sum of distances from a given set of point sites. More complex problems considered in this discipline include the placement of multiple facilities, constraints on the locations of facilities, and more complex optimization criteria.
3208:
Municipal solid waste management still remains a challenge for developing countries because of increasing waste production and high costs associated with waste management. Through the formulation and exact resolution of a facility location problem it is possible to optimize the location of landfills
3199:
In healthcare, incorrect facility location decisions have a serious impact on the community beyond simple cost and service metrics; for instance, hard-to-access healthcare facilities are likely to be associated with increased morbidity and mortality. From this perspective, facility location modeling
3248:
To see how one might view (read "transform" or "reduce") a centroid-based clustering problem as a (metric) facility location problem, view each data point in the former as a demand point in the latter. Suppose that the data to be clustered are elements of a metric space
3762:
yield different variants of the facility location problem, and hence different variants of the centroid-based clustering problem. For example, one might choose to minimize the sum of distances from each location to each of its assigned demand points (Ă la the
3160:
3065:
134:
concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors' facilities. The techniques also apply to
3653:
215:
problem seeks a location which minimizes the maximum distance to the sites, where the distance from one point to the sites is the distance from the point to its nearest site. A formal definition is as follows:
3430:
equivalence classes (i.e. colors) each of which has a centroid. Let us see how a solution to our constructed facility location problem also achieves such a partition. A feasible solution is a non-empty subset
3186:
constraints. In the capacitated case, these formulations are not equivalent. More information about the uncapacitated facility location problem can be found in
Chapter 3 of "Discrete location theory".
545:
3695:
provides a related problem-description and an approximation algorithm. The authors refer to the metric facility location problem (i.e. the centroid-based clustering problem or the metric
614:
It is easy to see that this algorithm runs in linear time. As approximation with factor less than 2 is proved to be NP hard, FPC was regarded as the best approximation one can find.
3070:
203:
problem. The MFL is still NP-hard and hard to approximate within factor better than 1.463. The currently best known approximation algorithm achieves approximation ratio of 1.488.
599:
For the hardness of the problem, it's impractical to get an exact solution or precise approximation. Instead, an approximation with factor = 2 is widely used for large
3460:
442:
290:
253:
2117:
2155:
1426:
1388:
1234:
1063:
978:
940:
832:
3686:
3404:
2977:
607:. The algorithm is quite simple: pick any point from the set as one center; search for the farthest point from remaining set as another center; repeat the process until
3547:
2350:
2274:
2033:
581:
2915:
1977:
1320:
1267:
2945:
2238:
2205:
1350:
862:
4558:
1453:
1196:
1137:
1090:
1005:
774:
4553:
2882:
3760:
3740:
3713:
3567:
3520:
3500:
3480:
3428:
3371:
3351:
3331:
3307:
3287:
3267:
3239:
3184:
2972:
2856:
2836:
2314:
2294:
2175:
2073:
2053:
1997:
1473:
1287:
1161:
1110:
1025:
902:
882:
794:
747:
727:
707:
687:
4149:
HWang, R. Z.; Chang, R. C.; Lee, R. C. T. (1993), "The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time",
166:
of facilities to open, to minimize the sum of distances from each demand point to its nearest facility, plus the sum of opening costs of the facilities.
39:
391:-center problem approximation is NP hard when approximation factor is less than 1.822 (dimension = 2) or 2 (dimension > 2).
3572:
4041:
4342:
4289:
3951:
3245:âsuch that points of the same color are close to one another (equivalently, such that points of different colors are far from one another).
86:
4297:
3805:
3333:). In the facility location problem that we are constructing, we permit facilities to be placed at any point within this metric space
387:
is measured as an approximation factor, which is defined as the ratio between the approximation and the optimum. It's proved that the
193:
180:
Without assumptions on the set of distances between clients and sites (in particular, without assuming that the distances satisfy the
58:
4431:
Franco, D. G. B.; Steiner, M. T. A.; Assef, F. M. (2020). "Optimization in waste landfilling partitioning in ParanĂĄ State, Brazil".
4366:
3925:
3800:
641:
problem seeks a location which maximizes the minimum distance to the sites. In the case of the
Euclidean metric, it is known as the
105:
65:
3998:
583:. The author claims that the running time is much less than the worst case and thus it's possible to solve some problems when
383:
problem is NP hard. Approximation to the problem was found to be also NP hard when the error is small. The error level in the
4213:
4092:
43:
3221:
problems can be viewed as facility location problems. In a centroid-based clustering problem, the objective is to partition
199:
If we assume distances between clients and sites are undirected and satisfy the triangle inequality, we are talking about a
72:
475:
4115:
HWang, R. Z.; Lee, R. C. T.; Chang, R. C. (1993), "The slab dividing approach to solve the
Euclidean p-center problem",
3785:
177:. A number of approximation algorithms have been developed for the facility location problem and many of its variants.
54:
3967:
Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L. (1981), "Optimal packing and covering in the plane are NP-complete",
4527:
4563:
4390:
4192:
32:
362:
351:
3166:
relaxation than the first formulation. Notice that summing the new constraints together yields the original big-
3840:
604:
3655:(break ties arbitrarily). This achieves the partitioning provided that the facility location problem's costs
3810:
3795:
384:
377:
3722:
Furthermore, see that in our above definition of the facility location problem that the objective function
749:
customers, in order to satisfy some fixed demand at minimum cost. We introduce the following notation: let
3929:
3884:
131:
3688:
are defined such that they are the images of the centroid-based clustering problem's distance function.
407:
79:
266:
229:
646:
642:
3934:
3162:
In practice, this new formulation performs significantly better, in the sense that it has a tighter
2086:
154:
In a basic formulation, the facility location problem consists of a set of potential facility sites
4269:
4036:
3889:
3790:
3434:
666:
181:
127:
3920:
Li, S. (2011). "A 1.488 Approximation
Algorithm for the Uncapacitated Facility Location Problem".
2122:
1393:
1355:
1201:
1030:
945:
907:
799:
4448:
4384:
4273:
4219:
4166:
4132:
4098:
3902:
3857:
3658:
3376:
3163:
460:
approximation is to find a solution with approximation factor no greater than 1 +
404:
There exist algorithms to produce exact solutions to this problem. One exact solver runs in time
3525:
4372:
4362:
4338:
4285:
4209:
4088:
3947:
3835:
2319:
2243:
2002:
550:
174:
3155:{\displaystyle z_{ij}\leqslant x_{i}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m}
2887:
1949:
1292:
1239:
603:
cases. The approximation is referred to as the farthest-point clustering (FPC) algorithm, or
4440:
4413:
4330:
4252:
4201:
4184:
4158:
4124:
4080:
4050:
4013:
3976:
3939:
3894:
3875:
Guha, S.; Khuller, S. (1999). "Greedy
Strikes Back: Improved Facility Location Algorithms".
3849:
3815:
3768:
3218:
2920:
2213:
2180:
1325:
837:
669:. In this context, facility location problems are often posed as follows: suppose there are
355:
136:
4499:
4404:
Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "A Survey of
Healthcare Facility Location".
1431:
1174:
1115:
1068:
983:
752:
3407:
3310:
650:
366:
2861:
2177:
from the nearest open facility. Because of this, we may replace the continuous variables
547:. As an alternative, another algorithm also based on core sets is available. It runs in
4278:
3994:
3745:
3725:
3698:
3552:
3505:
3485:
3465:
3413:
3356:
3336:
3316:
3292:
3272:
3252:
3224:
3169:
2957:
2841:
2821:
2299:
2279:
2160:
2058:
2038:
1982:
1458:
1272:
1146:
1095:
1010:
887:
867:
779:
732:
712:
692:
672:
4073:
Feder, TomĂĄs; Greene, Daniel (1988), "Optimal algorithms for approximate clustering",
3241:
data points (elements of a common metric space) into equivalence classesâoften called
2950:
Another formulation possibility for the uncapacitated facility location problem is to
4547:
4452:
4294:. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989.
4055:
4017:
3980:
3764:
148:
4223:
4170:
4136:
4076:
Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88
3906:
3861:
3780:
3060:{\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1,\dots ,n}
4444:
4102:
4074:
3502:
centroids in our centroid-based clustering problem. Now, assign each demand point
2083:
A common case of the capacitated facility location problem above is the case when
4237:
2858:
can affect computation resultsâthe best choice in this instance is obvious: take
4532:
4521:
4188:
3943:
2208:
2157:. In this case, it is always optimal to satisfy all of the demand from customer
617:
As per the performance of execution, the time complexity is later improved to O(
21:
2364:
1487:
4417:
4334:
4308:
G. T. Toussaint, "Computing largest empty circles with location constraints,"
4256:
3767:), or one might elect to minimize the maximum of all such distances (Ă la the
3482:
locations. These locations in our facility location problem comprise a set of
4376:
3406:
to be the pairwise distances between location-demand point pairs (e.g., see
4194:
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
3898:
4205:
3648:{\displaystyle \ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\ell ,d}\}}
729:
facilities to open, and (2) which (open) facilities to use to supply the
4084:
3410:). In a centroid-based clustering problem, one partitions the data into
4511:
4508:
4162:
4128:
3853:
3200:
for healthcare is more critical than similar modeling for other areas.
469:
170:
1092:
denote the maximum amount of product that can be produced by facility
4502:
4039:(1985), "Clustering to minimize the maximum intercluster distance",
4245:
International
Journal of Computational Geometry & Applications
3549:
that minimizes its servicing-cost; that is, assign the data point
2055:, that is, no demand for any customer can be filled from facility
4325:
Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014).
4517:
1065:. Further suppose that each facility has a maximum output. Let
4361:. Mirchandani, Pitu B., Francis, R. L. New York: Wiley. 1990.
3999:"On the complexity of locating linear facilities in the plane"
15:
4540:, a MATLAB-based tool for solving facility location problems.
4466:
Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009).
4537:
158:
where a facility can be opened, and a set of demand points
4514:, a professional society concerned with facility location.
4310:
International
Journal of Computer and Information Sciences
2838:
is a constant chosen to be suitably large. The choice of
3838:(1982). "Heuristics for the fixed cost median problem".
1946:
Note that the second set of constraints ensures that if
1171:
In our initial formulation, introduce a binary variable
173:
to solve optimally, by reduction from (for example) the
188:
and can be approximated to within a factor O(log
4533:
Web-based facility location utility (single facility)
3748:
3728:
3701:
3661:
3575:
3555:
3528:
3508:
3488:
3468:
3437:
3416:
3379:
3359:
3353:; this defines the set of allowed facility locations
3339:
3319:
3295:
3275:
3255:
3227:
3172:
3073:
2980:
2960:
2923:
2890:
2864:
2844:
2824:
2580:
2507:
2372:
2362:
2322:
2302:
2282:
2246:
2216:
2183:
2163:
2125:
2089:
2061:
2041:
2005:
1985:
1952:
1703:
1630:
1495:
1485:
1461:
1434:
1396:
1358:
1328:
1295:
1275:
1242:
1204:
1177:
1149:
1118:
1098:
1071:
1033:
1013:
986:
948:
910:
890:
870:
840:
802:
782:
755:
735:
715:
695:
675:
553:
478:
410:
269:
232:
540:{\displaystyle O(2^{O(k\log k/\varepsilon ^{2})}dn)}
162:
that must be serviced. The goal is to pick a subset
4238:"Almost optimal solutions to k-clustering problems"
169:The facility location problem on general graphs is
46:. Unsourced material may be challenged and removed.
4277:
3754:
3734:
3707:
3680:
3647:
3561:
3541:
3514:
3494:
3474:
3454:
3422:
3398:
3365:
3345:
3325:
3301:
3281:
3261:
3233:
3178:
3154:
3059:
2966:
2939:
2909:
2876:
2850:
2830:
2808:
2344:
2308:
2288:
2268:
2232:
2199:
2169:
2149:
2111:
2067:
2047:
2027:
1991:
1971:
1936:
1467:
1447:
1420:
1382:
1344:
1314:
1281:
1261:
1228:
1190:
1155:
1131:
1104:
1084:
1057:
1019:
999:
972:
934:
896:
876:
856:
826:
788:
768:
741:
721:
701:
681:
575:
539:
472:concept is proposed with execution complexity of
436:
284:
247:
358:. Its study traced at least to the year of 1860.
4329:. Graduate Texts in Mathematics. Vol. 271.
4191:(2002), "Approximate clustering via core-sets",
2367:
1490:
864:denote the cost to ship a product from facility
665:Facility location problems are often solved as
4031:
4029:
4027:
2974:constraints). That is, replace the constraints
709:customers. We wish to choose (1) which of the
4312:, vol. 12, No. 5, October, 1983, pp. 347â358.
8:
3642:
3623:
2947:will satisfy the second set of constraints.
2773:
2761:
2688:
2676:
1901:
1889:
1428:which represents the fraction of the demand
776:denote the (fixed) cost of opening facility
4068:
4066:
1322:otherwise. Further introduce the variable
376:It has been proven that exact solution of
147:A simple facility location problem is the
4503:EURO Working Group on Locational Analysis
4054:
3933:
3888:
3747:
3727:
3700:
3666:
3660:
3630:
3611:
3600:
3590:
3580:
3574:
3554:
3533:
3527:
3507:
3487:
3467:
3436:
3415:
3384:
3378:
3358:
3338:
3318:
3294:
3274:
3254:
3226:
3171:
3126:
3100:
3094:
3078:
3072:
3031:
3025:
3006:
2996:
2985:
2979:
2959:
2928:
2922:
2895:
2889:
2863:
2843:
2823:
2776:
2752:
2717:
2691:
2664:
2631:
2625:
2606:
2596:
2585:
2548:
2533:
2523:
2512:
2500:
2489:
2479:
2469:
2458:
2442:
2432:
2419:
2409:
2398:
2388:
2377:
2363:
2361:
2327:
2321:
2301:
2281:
2251:
2245:
2221:
2215:
2188:
2182:
2162:
2124:
2094:
2088:
2060:
2040:
2010:
2004:
1984:
1957:
1951:
1904:
1880:
1845:
1819:
1804:
1771:
1765:
1755:
1739:
1729:
1719:
1708:
1671:
1656:
1646:
1635:
1623:
1612:
1602:
1592:
1581:
1565:
1555:
1542:
1532:
1521:
1511:
1500:
1486:
1484:
1460:
1439:
1433:
1395:
1357:
1333:
1327:
1300:
1294:
1274:
1247:
1241:
1203:
1182:
1176:
1148:
1123:
1117:
1097:
1076:
1070:
1032:
1012:
991:
985:
947:
909:
889:
869:
845:
839:
801:
781:
760:
754:
734:
714:
694:
674:
564:
552:
517:
508:
489:
477:
422:
415:
409:
276:
272:
271:
268:
239:
235:
234:
231:
106:Learn how and when to remove this message
4280:Computational Geometry â An Introduction
3719:, thereby growing the list of synonyms.
1163:. The remainder of this section follows
468:is arbitrary. One approach based on the
343:In the case of the Euclidean metric for
3827:
2354:uncapacitated facility location problem
4559:Computational problems in graph theory
4382:
4554:Mathematical optimization in business
4320:
4318:
4236:Kumar, Pankaj; Kumar, Piyush (2010),
1477:capacitated facility location problem
7:
4481:Kleinberg, Jon; Tardos, Ăva (2006).
4468:The elements of statistical learning
625:) with box decomposition technique.
44:adding citations to reliable sources
4406:Computers & Operations Research
3922:Automata, Languages and Programming
464:. This approximation is NP hard as
3928:. Vol. 6756. pp. 77â88.
3806:Competitive facility location game
3607:
3604:
3601:
3597:
3594:
3591:
2954:the capacity constraints (the big-
2106:
437:{\displaystyle n^{O({\sqrt {k}})}}
194:approximation-preserving reduction
14:
4518:Bibliography on facility location
3801:List of spatial analysis software
4524:, containing over 3400 articles.
3742:is general. Specific choices of
3691:The popular algorithms textbook
661:Integer programming formulations
285:{\displaystyle \mathbb {R} ^{d}}
248:{\displaystyle \mathbb {R} ^{d}}
192:). This factor is tight, via an
120:facility location problems (FLP)
20:
2079:Uncapacitated facility location
31:needs additional citations for
4528:Library of location algorithms
3969:Information Processing Letters
2112:{\displaystyle u_{i}=+\infty }
1007:denote the demand of customer
570:
557:
534:
523:
493:
482:
429:
419:
201:metric facility location (MFL)
1:
4445:10.1016/j.jclepro.2020.125353
4433:Journal of Cleaner Production
3455:{\displaystyle L'\subseteq L}
1167:Capacitated facility location
4512:section on location analysis
4470:(Second ed.). Springer.
4056:10.1016/0304-3975(85)90224-5
4042:Theoretical Computer Science
4018:10.1016/0167-6377(82)90039-6
3981:10.1016/0020-0190(81)90111-3
3786:Quadratic assignment problem
2150:{\displaystyle i=1,\dots ,n}
1421:{\displaystyle j=1,\dots ,m}
1383:{\displaystyle i=1,\dots ,n}
1229:{\displaystyle i=1,\dots ,n}
1058:{\displaystyle j=1,\dots ,m}
973:{\displaystyle j=1,\dots ,m}
935:{\displaystyle i=1,\dots ,n}
827:{\displaystyle i=1,\dots ,n}
196:from the set cover problem.
186:non-metric facility location
4538:Facility Location Optimizer
4006:Operations Research Letters
3944:10.1007/978-3-642-22012-8_5
3681:{\displaystyle c_{\ell ,d}}
3399:{\displaystyle c_{\ell ,d}}
649:problem) may be solved in
639:obnoxious facility location
184:), the problem is known as
55:"Optimal facility location"
4580:
645:problem. The planar case (
360:
4418:10.1016/j.cor.2016.05.018
4335:10.1007/978-3-319-11008-0
4257:10.1142/S0218195910003372
3542:{\displaystyle \ell ^{*}}
595:Farthest-point clustering
363:Smallest enclosing circle
352:smallest enclosing sphere
213:minimax facility location
207:Minimax facility location
143:Minimum facility location
4359:Discrete location theory
3841:Mathematical Programming
3717:center selection problem
3715:-center problem) as the
2345:{\displaystyle z_{ij}=0}
2296:is supplied by facility
2269:{\displaystyle z_{ij}=1}
2028:{\displaystyle y_{ij}=0}
635:maxmin facility location
629:Maxmin facility location
605:farthest-first traversal
576:{\displaystyle O(k^{n})}
3811:Vertex k-center problem
3217:A particular subset of
2910:{\displaystyle x_{i}=1}
1972:{\displaystyle x_{i}=0}
1315:{\displaystyle x_{i}=0}
1262:{\displaystyle x_{i}=1}
385:approximation algorithm
4389:: CS1 maint: others (
3997:; Tamir, Arie (1982),
3899:10.1006/jagm.1998.0993
3756:
3736:
3709:
3682:
3649:
3563:
3543:
3516:
3496:
3476:
3456:
3424:
3400:
3373:. We define the costs
3367:
3347:
3327:
3303:
3283:
3263:
3235:
3204:Solid waste management
3180:
3156:
3061:
3001:
2968:
2941:
2940:{\displaystyle z_{ij}}
2911:
2878:
2852:
2832:
2810:
2601:
2528:
2474:
2414:
2393:
2346:
2310:
2290:
2270:
2234:
2233:{\displaystyle z_{ij}}
2201:
2200:{\displaystyle y_{ij}}
2171:
2151:
2113:
2069:
2049:
2029:
1993:
1973:
1938:
1724:
1651:
1597:
1537:
1516:
1469:
1449:
1422:
1384:
1346:
1345:{\displaystyle y_{ij}}
1316:
1283:
1263:
1230:
1192:
1157:
1133:
1106:
1086:
1059:
1021:
1001:
974:
936:
898:
878:
858:
857:{\displaystyle c_{ij}}
828:
790:
770:
743:
723:
703:
683:
577:
541:
438:
286:
249:
132:computational geometry
4206:10.1145/509907.509947
3877:Journal of Algorithms
3757:
3737:
3710:
3683:
3650:
3564:
3544:
3517:
3497:
3477:
3457:
3425:
3401:
3368:
3348:
3328:
3304:
3284:
3264:
3236:
3181:
3157:
3062:
2981:
2969:
2942:
2912:
2879:
2853:
2833:
2811:
2581:
2508:
2454:
2394:
2373:
2347:
2311:
2291:
2271:
2235:
2202:
2172:
2152:
2114:
2070:
2050:
2030:
1994:
1974:
1939:
1704:
1631:
1577:
1517:
1496:
1470:
1450:
1448:{\displaystyle d_{j}}
1423:
1385:
1347:
1317:
1284:
1264:
1231:
1193:
1191:{\displaystyle x_{i}}
1158:
1134:
1132:{\displaystyle u_{i}}
1107:
1087:
1085:{\displaystyle u_{i}}
1060:
1022:
1002:
1000:{\displaystyle d_{j}}
975:
937:
899:
879:
859:
829:
791:
771:
769:{\displaystyle f_{i}}
744:
724:
704:
684:
578:
542:
439:
361:Further information:
350:, it is known as the
287:
250:
4200:, pp. 250â257,
4079:, pp. 434â444,
3796:Dijkstra's algorithm
3746:
3726:
3699:
3659:
3573:
3553:
3526:
3506:
3486:
3466:
3435:
3414:
3377:
3357:
3337:
3317:
3293:
3273:
3253:
3225:
3209:for waste disposal.
3170:
3071:
3067:with the constraints
2978:
2958:
2921:
2917:, any choice of the
2888:
2862:
2842:
2822:
2360:
2320:
2300:
2280:
2244:
2214:
2207:from above with the
2181:
2161:
2123:
2087:
2059:
2039:
2003:
1983:
1979:, that is, facility
1950:
1483:
1459:
1432:
1394:
1356:
1326:
1293:
1273:
1240:
1202:
1175:
1147:
1116:
1096:
1069:
1031:
1011:
984:
946:
908:
888:
868:
838:
800:
780:
753:
733:
713:
693:
673:
647:largest empty circle
643:largest empty sphere
591: < 5).
551:
476:
408:
267:
230:
40:improve this article
4327:Integer Programming
4284:. Springer-Verlag.
4270:Franco P. Preparata
4085:10.1145/62212.62255
3791:Location-allocation
3102: for all
3033: for all
2877:{\displaystyle M=m}
2778: for all
2693: for all
2633: for all
2550: for all
1906: for all
1821: for all
1773: for all
1673: for all
1455:filled by facility
657: log n).
611:centers are found.
587:is small (say
256:, find a point set
182:triangle inequality
128:operations research
4274:Michael Ian Shamos
4163:10.1007/bf01228511
4129:10.1007/BF01185335
3854:10.1007/BF01581035
3752:
3732:
3705:
3678:
3645:
3559:
3539:
3512:
3492:
3472:
3452:
3420:
3396:
3363:
3343:
3323:
3299:
3279:
3259:
3231:
3176:
3164:Linear programming
3152:
3057:
2964:
2937:
2907:
2874:
2848:
2828:
2806:
2804:
2654:
2574:
2495:
2342:
2306:
2286:
2266:
2230:
2197:
2167:
2147:
2109:
2065:
2045:
2025:
1989:
1969:
1934:
1932:
1794:
1697:
1618:
1465:
1445:
1418:
1380:
1342:
1312:
1279:
1259:
1226:
1188:
1153:
1129:
1102:
1082:
1055:
1017:
997:
970:
932:
894:
874:
854:
824:
786:
766:
739:
719:
699:
679:
573:
537:
434:
282:
245:
219:Given a point set
4564:Facility location
4344:978-3-319-11007-3
4291:978-0-387-96131-6
4185:Har-Peled, Sariel
4037:Gonzalez, Teofilo
3953:978-3-642-22011-1
3755:{\displaystyle f}
3735:{\displaystyle f}
3708:{\displaystyle k}
3562:{\displaystyle d}
3515:{\displaystyle d}
3495:{\displaystyle k}
3475:{\displaystyle k}
3423:{\displaystyle k}
3366:{\displaystyle L}
3346:{\displaystyle M}
3326:{\displaystyle p}
3302:{\displaystyle p}
3282:{\displaystyle M}
3262:{\displaystyle M}
3234:{\displaystyle n}
3179:{\displaystyle M}
3129:
3103:
3034:
2967:{\displaystyle M}
2851:{\displaystyle M}
2831:{\displaystyle M}
2779:
2720:
2694:
2634:
2551:
2503:
2309:{\displaystyle i}
2289:{\displaystyle j}
2170:{\displaystyle j}
2068:{\displaystyle i}
2048:{\displaystyle j}
1999:isn't open, then
1992:{\displaystyle i}
1907:
1848:
1822:
1774:
1674:
1626:
1468:{\displaystyle i}
1282:{\displaystyle i}
1156:{\displaystyle i}
1105:{\displaystyle i}
1020:{\displaystyle j}
897:{\displaystyle j}
877:{\displaystyle i}
789:{\displaystyle i}
742:{\displaystyle m}
722:{\displaystyle n}
702:{\displaystyle m}
682:{\displaystyle n}
427:
175:set cover problem
126:, is a branch of
124:location analysis
116:
115:
108:
90:
4571:
4487:
4486:
4483:Algorithm Design
4478:
4472:
4471:
4463:
4457:
4456:
4428:
4422:
4421:
4401:
4395:
4394:
4388:
4380:
4355:
4349:
4348:
4322:
4313:
4306:
4300:
4295:
4283:
4266:
4260:
4259:
4242:
4233:
4227:
4226:
4199:
4180:
4174:
4173:
4146:
4140:
4139:
4112:
4106:
4105:
4070:
4061:
4059:
4058:
4033:
4022:
4020:
4003:
3991:
3985:
3983:
3964:
3958:
3957:
3937:
3917:
3911:
3910:
3892:
3872:
3866:
3865:
3832:
3816:geometric median
3769:1-center problem
3761:
3759:
3758:
3753:
3741:
3739:
3738:
3733:
3714:
3712:
3711:
3706:
3693:Algorithm Design
3687:
3685:
3684:
3679:
3677:
3676:
3654:
3652:
3651:
3646:
3641:
3640:
3622:
3621:
3610:
3585:
3584:
3569:to the centroid
3568:
3566:
3565:
3560:
3548:
3546:
3545:
3540:
3538:
3537:
3522:to the location
3521:
3519:
3518:
3513:
3501:
3499:
3498:
3493:
3481:
3479:
3478:
3473:
3461:
3459:
3458:
3453:
3445:
3429:
3427:
3426:
3421:
3405:
3403:
3402:
3397:
3395:
3394:
3372:
3370:
3369:
3364:
3352:
3350:
3349:
3344:
3332:
3330:
3329:
3324:
3308:
3306:
3305:
3300:
3288:
3286:
3285:
3280:
3268:
3266:
3265:
3260:
3240:
3238:
3237:
3232:
3219:cluster analysis
3185:
3183:
3182:
3177:
3161:
3159:
3158:
3153:
3130:
3127:
3104:
3101:
3099:
3098:
3086:
3085:
3066:
3064:
3063:
3058:
3035:
3032:
3030:
3029:
3014:
3013:
3000:
2995:
2973:
2971:
2970:
2965:
2946:
2944:
2943:
2938:
2936:
2935:
2916:
2914:
2913:
2908:
2900:
2899:
2883:
2881:
2880:
2875:
2857:
2855:
2854:
2849:
2837:
2835:
2834:
2829:
2815:
2813:
2812:
2807:
2805:
2780:
2777:
2757:
2756:
2746:
2721:
2718:
2695:
2692:
2672:
2671:
2658:
2635:
2632:
2630:
2629:
2614:
2613:
2600:
2595:
2578:
2552:
2549:
2541:
2540:
2527:
2522:
2504:
2501:
2494:
2493:
2484:
2483:
2473:
2468:
2450:
2449:
2437:
2436:
2427:
2426:
2413:
2408:
2392:
2387:
2356:is then given by
2351:
2349:
2348:
2343:
2335:
2334:
2315:
2313:
2312:
2307:
2295:
2293:
2292:
2287:
2275:
2273:
2272:
2267:
2259:
2258:
2239:
2237:
2236:
2231:
2229:
2228:
2209:binary variables
2206:
2204:
2203:
2198:
2196:
2195:
2176:
2174:
2173:
2168:
2156:
2154:
2153:
2148:
2118:
2116:
2115:
2110:
2099:
2098:
2074:
2072:
2071:
2066:
2054:
2052:
2051:
2046:
2034:
2032:
2031:
2026:
2018:
2017:
1998:
1996:
1995:
1990:
1978:
1976:
1975:
1970:
1962:
1961:
1943:
1941:
1940:
1935:
1933:
1908:
1905:
1885:
1884:
1874:
1849:
1846:
1823:
1820:
1812:
1811:
1798:
1775:
1772:
1770:
1769:
1760:
1759:
1747:
1746:
1734:
1733:
1723:
1718:
1701:
1675:
1672:
1664:
1663:
1650:
1645:
1627:
1624:
1617:
1616:
1607:
1606:
1596:
1591:
1573:
1572:
1560:
1559:
1550:
1549:
1536:
1531:
1515:
1510:
1479:is then given by
1475:. The so-called
1474:
1472:
1471:
1466:
1454:
1452:
1451:
1446:
1444:
1443:
1427:
1425:
1424:
1419:
1389:
1387:
1386:
1381:
1351:
1349:
1348:
1343:
1341:
1340:
1321:
1319:
1318:
1313:
1305:
1304:
1288:
1286:
1285:
1280:
1268:
1266:
1265:
1260:
1252:
1251:
1235:
1233:
1232:
1227:
1197:
1195:
1194:
1189:
1187:
1186:
1162:
1160:
1159:
1154:
1138:
1136:
1135:
1130:
1128:
1127:
1111:
1109:
1108:
1103:
1091:
1089:
1088:
1083:
1081:
1080:
1064:
1062:
1061:
1056:
1026:
1024:
1023:
1018:
1006:
1004:
1003:
998:
996:
995:
979:
977:
976:
971:
941:
939:
938:
933:
903:
901:
900:
895:
883:
881:
880:
875:
863:
861:
860:
855:
853:
852:
833:
831:
830:
825:
795:
793:
792:
787:
775:
773:
772:
767:
765:
764:
748:
746:
745:
740:
728:
726:
725:
720:
708:
706:
705:
700:
688:
686:
685:
680:
667:integer programs
582:
580:
579:
574:
569:
568:
546:
544:
543:
538:
527:
526:
522:
521:
512:
443:
441:
440:
435:
433:
432:
428:
423:
356:1-center problem
349:
339:
303:
291:
289:
288:
283:
281:
280:
275:
255:
254:
252:
251:
246:
244:
243:
238:
137:cluster analysis
122:, also known as
111:
104:
100:
97:
91:
89:
48:
24:
16:
4579:
4578:
4574:
4573:
4572:
4570:
4569:
4568:
4544:
4543:
4496:
4491:
4490:
4480:
4479:
4475:
4465:
4464:
4460:
4430:
4429:
4425:
4403:
4402:
4398:
4381:
4369:
4357:
4356:
4352:
4345:
4324:
4323:
4316:
4307:
4303:
4292:
4268:
4267:
4263:
4240:
4235:
4234:
4230:
4216:
4197:
4183:BÄdoiu, Mihai;
4182:
4181:
4177:
4148:
4147:
4143:
4114:
4113:
4109:
4095:
4072:
4071:
4064:
4035:
4034:
4025:
4001:
3995:Megiddo, Nimrod
3993:
3992:
3988:
3966:
3965:
3961:
3954:
3935:10.1.1.225.6387
3919:
3918:
3914:
3874:
3873:
3869:
3836:Hochbaum, D. S.
3834:
3833:
3829:
3824:
3777:
3744:
3743:
3724:
3723:
3697:
3696:
3662:
3657:
3656:
3626:
3589:
3576:
3571:
3570:
3551:
3550:
3529:
3524:
3523:
3504:
3503:
3484:
3483:
3464:
3463:
3438:
3433:
3432:
3412:
3411:
3408:metric k-center
3380:
3375:
3374:
3355:
3354:
3335:
3334:
3315:
3314:
3313:for some fixed
3311:Euclidean space
3291:
3290:
3271:
3270:
3251:
3250:
3223:
3222:
3215:
3206:
3197:
3192:
3168:
3167:
3128: and
3090:
3074:
3069:
3068:
3021:
3002:
2976:
2975:
2956:
2955:
2924:
2919:
2918:
2891:
2886:
2885:
2860:
2859:
2840:
2839:
2820:
2819:
2803:
2802:
2748:
2744:
2743:
2719: and
2660:
2656:
2655:
2621:
2602:
2576:
2575:
2529:
2505:
2497:
2496:
2485:
2475:
2438:
2428:
2415:
2370:
2358:
2357:
2352:otherwise. The
2323:
2318:
2317:
2298:
2297:
2278:
2277:
2247:
2242:
2241:
2217:
2212:
2211:
2184:
2179:
2178:
2159:
2158:
2121:
2120:
2090:
2085:
2084:
2081:
2057:
2056:
2037:
2036:
2006:
2001:
2000:
1981:
1980:
1953:
1948:
1947:
1931:
1930:
1876:
1872:
1871:
1847: and
1800:
1796:
1795:
1761:
1751:
1735:
1725:
1699:
1698:
1652:
1628:
1620:
1619:
1608:
1598:
1561:
1551:
1538:
1493:
1481:
1480:
1457:
1456:
1435:
1430:
1429:
1392:
1391:
1354:
1353:
1329:
1324:
1323:
1296:
1291:
1290:
1271:
1270:
1243:
1238:
1237:
1200:
1199:
1178:
1173:
1172:
1169:
1145:
1144:
1119:
1114:
1113:
1112:, that is, let
1094:
1093:
1072:
1067:
1066:
1029:
1028:
1009:
1008:
987:
982:
981:
944:
943:
906:
905:
886:
885:
866:
865:
841:
836:
835:
798:
797:
778:
777:
756:
751:
750:
731:
730:
711:
710:
691:
690:
689:facilities and
671:
670:
663:
631:
621: log
560:
549:
548:
513:
485:
474:
473:
411:
406:
405:
397:
374:
369:
367:Bounding sphere
344:
329:
317:
305:
270:
265:
264:
257:
233:
228:
227:
220:
209:
145:
112:
101:
95:
92:
49:
47:
37:
25:
12:
11:
5:
4577:
4575:
4567:
4566:
4561:
4556:
4546:
4545:
4542:
4541:
4535:
4530:
4525:
4515:
4506:
4495:
4494:External links
4492:
4489:
4488:
4473:
4458:
4423:
4396:
4367:
4350:
4343:
4314:
4301:
4290:
4261:
4251:(4): 431â447,
4228:
4214:
4175:
4157:(4): 398â423,
4141:
4107:
4093:
4062:
4023:
4012:(5): 194â197,
3986:
3975:(3): 133â137,
3959:
3952:
3912:
3890:10.1.1.47.2033
3867:
3826:
3825:
3823:
3820:
3819:
3818:
3813:
3808:
3803:
3798:
3793:
3788:
3783:
3776:
3773:
3751:
3731:
3704:
3675:
3672:
3669:
3665:
3644:
3639:
3636:
3633:
3629:
3625:
3620:
3617:
3614:
3609:
3606:
3603:
3599:
3596:
3593:
3588:
3583:
3579:
3558:
3536:
3532:
3511:
3491:
3471:
3451:
3448:
3444:
3441:
3419:
3393:
3390:
3387:
3383:
3362:
3342:
3322:
3298:
3278:
3258:
3230:
3214:
3211:
3205:
3202:
3196:
3193:
3191:
3188:
3175:
3151:
3148:
3145:
3142:
3139:
3136:
3133:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3097:
3093:
3089:
3084:
3081:
3077:
3056:
3053:
3050:
3047:
3044:
3041:
3038:
3028:
3024:
3020:
3017:
3012:
3009:
3005:
2999:
2994:
2991:
2988:
2984:
2963:
2934:
2931:
2927:
2906:
2903:
2898:
2894:
2873:
2870:
2867:
2847:
2827:
2801:
2798:
2795:
2792:
2789:
2786:
2783:
2775:
2772:
2769:
2766:
2763:
2760:
2755:
2751:
2747:
2745:
2742:
2739:
2736:
2733:
2730:
2727:
2724:
2716:
2713:
2710:
2707:
2704:
2701:
2698:
2690:
2687:
2684:
2681:
2678:
2675:
2670:
2667:
2663:
2659:
2657:
2653:
2650:
2647:
2644:
2641:
2638:
2628:
2624:
2620:
2617:
2612:
2609:
2605:
2599:
2594:
2591:
2588:
2584:
2579:
2577:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2547:
2544:
2539:
2536:
2532:
2526:
2521:
2518:
2515:
2511:
2506:
2499:
2498:
2492:
2488:
2482:
2478:
2472:
2467:
2464:
2461:
2457:
2453:
2448:
2445:
2441:
2435:
2431:
2425:
2422:
2418:
2412:
2407:
2404:
2401:
2397:
2391:
2386:
2383:
2380:
2376:
2371:
2369:
2366:
2365:
2341:
2338:
2333:
2330:
2326:
2305:
2285:
2265:
2262:
2257:
2254:
2250:
2227:
2224:
2220:
2194:
2191:
2187:
2166:
2146:
2143:
2140:
2137:
2134:
2131:
2128:
2108:
2105:
2102:
2097:
2093:
2080:
2077:
2064:
2044:
2024:
2021:
2016:
2013:
2009:
1988:
1968:
1965:
1960:
1956:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1903:
1900:
1897:
1894:
1891:
1888:
1883:
1879:
1875:
1873:
1870:
1867:
1864:
1861:
1858:
1855:
1852:
1844:
1841:
1838:
1835:
1832:
1829:
1826:
1818:
1815:
1810:
1807:
1803:
1799:
1797:
1793:
1790:
1787:
1784:
1781:
1778:
1768:
1764:
1758:
1754:
1750:
1745:
1742:
1738:
1732:
1728:
1722:
1717:
1714:
1711:
1707:
1702:
1700:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1670:
1667:
1662:
1659:
1655:
1649:
1644:
1641:
1638:
1634:
1629:
1622:
1621:
1615:
1611:
1605:
1601:
1595:
1590:
1587:
1584:
1580:
1576:
1571:
1568:
1564:
1558:
1554:
1548:
1545:
1541:
1535:
1530:
1527:
1524:
1520:
1514:
1509:
1506:
1503:
1499:
1494:
1492:
1489:
1488:
1464:
1442:
1438:
1417:
1414:
1411:
1408:
1405:
1402:
1399:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1339:
1336:
1332:
1311:
1308:
1303:
1299:
1278:
1258:
1255:
1250:
1246:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1185:
1181:
1168:
1165:
1152:
1126:
1122:
1101:
1079:
1075:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1016:
994:
990:
969:
966:
963:
960:
957:
954:
951:
931:
928:
925:
922:
919:
916:
913:
893:
873:
851:
848:
844:
823:
820:
817:
814:
811:
808:
805:
785:
763:
759:
738:
718:
698:
678:
662:
659:
630:
627:
572:
567:
563:
559:
556:
536:
533:
530:
525:
520:
516:
511:
507:
504:
501:
498:
495:
492:
488:
484:
481:
456:1 +
431:
426:
421:
418:
414:
396:
393:
373:
370:
340:is minimized.
319:
307:
279:
274:
242:
237:
208:
205:
144:
141:
114:
113:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
4576:
4565:
4562:
4560:
4557:
4555:
4552:
4551:
4549:
4539:
4536:
4534:
4531:
4529:
4526:
4523:
4520:collected by
4519:
4516:
4513:
4510:
4507:
4504:
4501:
4498:
4497:
4493:
4484:
4477:
4474:
4469:
4462:
4459:
4454:
4450:
4446:
4442:
4438:
4434:
4427:
4424:
4419:
4415:
4411:
4407:
4400:
4397:
4392:
4386:
4378:
4374:
4370:
4368:9780471892335
4364:
4360:
4354:
4351:
4346:
4340:
4336:
4332:
4328:
4321:
4319:
4315:
4311:
4305:
4302:
4299:
4293:
4287:
4282:
4281:
4275:
4271:
4265:
4262:
4258:
4254:
4250:
4246:
4239:
4232:
4229:
4225:
4221:
4217:
4211:
4207:
4203:
4196:
4195:
4190:
4186:
4179:
4176:
4172:
4168:
4164:
4160:
4156:
4152:
4145:
4142:
4138:
4134:
4130:
4126:
4122:
4118:
4111:
4108:
4104:
4100:
4096:
4090:
4086:
4082:
4078:
4077:
4069:
4067:
4063:
4057:
4052:
4048:
4044:
4043:
4038:
4032:
4030:
4028:
4024:
4019:
4015:
4011:
4007:
4000:
3996:
3990:
3987:
3982:
3978:
3974:
3970:
3963:
3960:
3955:
3949:
3945:
3941:
3936:
3931:
3927:
3923:
3916:
3913:
3908:
3904:
3900:
3896:
3891:
3886:
3882:
3878:
3871:
3868:
3863:
3859:
3855:
3851:
3847:
3843:
3842:
3837:
3831:
3828:
3821:
3817:
3814:
3812:
3809:
3807:
3804:
3802:
3799:
3797:
3794:
3792:
3789:
3787:
3784:
3782:
3779:
3778:
3774:
3772:
3770:
3766:
3765:Weber problem
3749:
3729:
3720:
3718:
3702:
3694:
3689:
3673:
3670:
3667:
3663:
3637:
3634:
3631:
3627:
3618:
3615:
3612:
3586:
3581:
3577:
3556:
3534:
3530:
3509:
3489:
3469:
3449:
3446:
3442:
3439:
3417:
3409:
3391:
3388:
3385:
3381:
3360:
3340:
3320:
3312:
3309:-dimensional
3296:
3276:
3256:
3246:
3244:
3228:
3220:
3212:
3210:
3203:
3201:
3194:
3189:
3187:
3173:
3165:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3123:
3120:
3117:
3114:
3111:
3108:
3105:
3095:
3091:
3087:
3082:
3079:
3075:
3054:
3051:
3048:
3045:
3042:
3039:
3036:
3026:
3022:
3018:
3015:
3010:
3007:
3003:
2997:
2992:
2989:
2986:
2982:
2961:
2953:
2948:
2932:
2929:
2925:
2904:
2901:
2896:
2892:
2871:
2868:
2865:
2845:
2825:
2816:
2799:
2796:
2793:
2790:
2787:
2784:
2781:
2770:
2767:
2764:
2758:
2753:
2749:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2714:
2711:
2708:
2705:
2702:
2699:
2696:
2685:
2682:
2679:
2673:
2668:
2665:
2661:
2651:
2648:
2645:
2642:
2639:
2636:
2626:
2622:
2618:
2615:
2610:
2607:
2603:
2597:
2592:
2589:
2586:
2582:
2571:
2568:
2565:
2562:
2559:
2556:
2553:
2545:
2542:
2537:
2534:
2530:
2524:
2519:
2516:
2513:
2509:
2490:
2486:
2480:
2476:
2470:
2465:
2462:
2459:
2455:
2451:
2446:
2443:
2439:
2433:
2429:
2423:
2420:
2416:
2410:
2405:
2402:
2399:
2395:
2389:
2384:
2381:
2378:
2374:
2355:
2339:
2336:
2331:
2328:
2324:
2303:
2283:
2263:
2260:
2255:
2252:
2248:
2225:
2222:
2218:
2210:
2192:
2189:
2185:
2164:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2103:
2100:
2095:
2091:
2078:
2076:
2062:
2042:
2022:
2019:
2014:
2011:
2007:
1986:
1966:
1963:
1958:
1954:
1944:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1898:
1895:
1892:
1886:
1881:
1877:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1816:
1813:
1808:
1805:
1801:
1791:
1788:
1785:
1782:
1779:
1776:
1766:
1762:
1756:
1752:
1748:
1743:
1740:
1736:
1730:
1726:
1720:
1715:
1712:
1709:
1705:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1668:
1665:
1660:
1657:
1653:
1647:
1642:
1639:
1636:
1632:
1613:
1609:
1603:
1599:
1593:
1588:
1585:
1582:
1578:
1574:
1569:
1566:
1562:
1556:
1552:
1546:
1543:
1539:
1533:
1528:
1525:
1522:
1518:
1512:
1507:
1504:
1501:
1497:
1478:
1462:
1440:
1436:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1377:
1374:
1371:
1368:
1365:
1362:
1359:
1337:
1334:
1330:
1309:
1306:
1301:
1297:
1289:is open, and
1276:
1256:
1253:
1248:
1244:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1183:
1179:
1166:
1164:
1150:
1142:
1124:
1120:
1099:
1077:
1073:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1014:
992:
988:
967:
964:
961:
958:
955:
952:
949:
929:
926:
923:
920:
917:
914:
911:
891:
871:
849:
846:
842:
821:
818:
815:
812:
809:
806:
803:
783:
761:
757:
736:
716:
696:
676:
668:
660:
658:
656:
652:
648:
644:
640:
636:
628:
626:
624:
620:
615:
612:
610:
606:
602:
597:
596:
592:
590:
586:
565:
561:
554:
531:
528:
518:
514:
509:
505:
502:
499:
496:
490:
486:
479:
471:
467:
463:
459:
454:
453:
452:approximation
451:
445:
424:
416:
412:
402:
401:
394:
392:
390:
386:
382:
380:
371:
368:
364:
359:
357:
353:
347:
341:
337:
333:
328:
327:
322:
316:
315:
310:
301:
297:
296:
277:
262:
261:
240:
225:
224:
217:
214:
206:
204:
202:
197:
195:
191:
187:
183:
178:
176:
172:
167:
165:
161:
157:
152:
150:
149:Weber problem
142:
140:
138:
133:
129:
125:
121:
118:The study of
110:
107:
99:
88:
85:
81:
78:
74:
71:
67:
64:
60:
57: â
56:
52:
51:Find sources:
45:
41:
35:
34:
29:This article
27:
23:
18:
17:
4482:
4476:
4467:
4461:
4436:
4432:
4426:
4409:
4405:
4399:
4358:
4353:
4326:
4309:
4304:
4279:
4264:
4248:
4244:
4231:
4193:
4189:Indyk, Piotr
4178:
4154:
4151:Algorithmica
4150:
4144:
4120:
4117:Algorithmica
4116:
4110:
4075:
4046:
4040:
4009:
4005:
3989:
3972:
3968:
3962:
3921:
3915:
3880:
3876:
3870:
3845:
3839:
3830:
3781:Graph center
3721:
3716:
3692:
3690:
3247:
3242:
3216:
3207:
3198:
3190:Applications
2952:disaggregate
2951:
2949:
2817:
2353:
2276:if customer
2082:
1945:
1476:
1269:if facility
1170:
1143:of facility
1140:
884:to customer
664:
654:
651:optimal time
638:
634:
632:
622:
618:
616:
613:
608:
600:
598:
594:
593:
588:
584:
465:
461:
457:
455:
449:
447:
446:
403:
400:Exact solver
399:
398:
388:
378:
375:
345:
342:
335:
331:
325:
324:
320:
313:
312:
308:
299:
294:
293:
259:
258:
222:
221:
218:
212:
210:
200:
198:
189:
185:
179:
168:
163:
159:
155:
153:
146:
123:
119:
117:
102:
93:
83:
76:
69:
62:
50:
38:Please help
33:verification
30:
4522:Trevor Hale
4412:: 223â263.
4298:p. 256
4123:(1): 1â22,
4049:: 293â306,
3883:: 228â248.
3848:: 148â162.
2884:. Then, if
1139:denote the
372:NP hardness
354:problem or
4548:Categories
4485:. Pearson.
4439:: 125353.
4215:1581134959
4094:0897912640
3822:References
3269:(e.g. let
3213:Clustering
3195:Healthcare
395:Algorithms
66:newspapers
4453:229429742
4385:cite book
3930:CiteSeerX
3885:CiteSeerX
3668:ℓ
3632:ℓ
3616:∈
3613:ℓ
3582:∗
3578:ℓ
3535:∗
3531:ℓ
3447:⊆
3386:ℓ
3144:…
3118:…
3088:⩽
3049:…
3016:⩽
2983:∑
2794:…
2759:∈
2735:…
2709:…
2674:∈
2646:…
2616:⩽
2583:∑
2566:…
2510:∑
2456:∑
2396:∑
2375:∑
2139:…
2107:∞
1922:…
1887:∈
1863:…
1837:…
1814:⩾
1786:…
1749:⩽
1706:∑
1689:…
1633:∑
1579:∑
1519:∑
1498:∑
1410:…
1372:…
1218:…
1047:…
962:…
924:…
816:…
515:ε
503:
298:| =
4377:19810449
4276:(1985).
3775:See also
3443:′
2240:, where
2119:for all
2035:for all
1236:, where
1141:capacity
304:so that
292:, |
96:May 2009
4509:INFORMS
4224:5409535
4171:2722869
4137:5680676
3907:5363214
3862:3451944
653:Θ(
470:coreset
381:-center
171:NP-hard
80:scholar
4451:
4375:
4365:
4341:
4288:
4222:
4212:
4169:
4135:
4103:658151
4101:
4091:
3950:
3932:
3905:
3887:
3860:
3243:colors
2818:where
2316:, and
980:. Let
834:. Let
796:, for
466:ε
462:ε
458:ε
450:ε
82:
75:
68:
61:
53:
4500:EWGLA
4449:S2CID
4241:(PDF)
4220:S2CID
4198:(PDF)
4167:S2CID
4133:S2CID
4099:S2CID
4002:(PDF)
3903:S2CID
3858:S2CID
87:JSTOR
73:books
4391:link
4373:OCLC
4363:ISBN
4339:ISBN
4286:ISBN
4272:and
4210:ISBN
4089:ISBN
3948:ISBN
3926:LNCS
2502:s.t.
1625:s.t.
1390:and
1352:for
1198:for
1027:for
942:and
904:for
633:The
448:1 +
365:and
338:)) )
318:(min
211:The
130:and
59:news
4441:doi
4437:283
4414:doi
4331:doi
4253:doi
4202:doi
4159:doi
4125:doi
4081:doi
4051:doi
4014:doi
3977:doi
3940:doi
3895:doi
3850:doi
3771:).
3462:of
3289:be
2368:min
1491:min
637:or
500:log
348:= 1
330:(d(
306:max
42:by
4550::
4447:.
4435:.
4410:79
4408:.
4387:}}
4383:{{
4371:.
4337:.
4317:^
4296:,
4249:20
4247:,
4243:,
4218:,
4208:,
4187:;
4165:,
4153:,
4131:,
4119:,
4097:,
4087:,
4065:^
4047:38
4045:,
4026:^
4008:,
4004:,
3973:12
3971:,
3946:.
3938:.
3924:.
3901:.
3893:.
3881:31
3879:.
3856:.
3846:22
3844:.
3587::=
2075:.
444:.
334:,
323:â
311:â
263:â
226:â
139:.
4505:.
4455:.
4443::
4420:.
4416::
4393:)
4379:.
4347:.
4333::
4255::
4204::
4161::
4155:9
4127::
4121:9
4083::
4060:.
4053::
4021:.
4016::
4010:1
3984:.
3979::
3956:.
3942::
3909:.
3897::
3864:.
3852::
3750:f
3730:f
3703:k
3674:d
3671:,
3664:c
3643:}
3638:d
3635:,
3628:c
3624:{
3619:L
3608:n
3605:i
3602:m
3598:g
3595:r
3592:a
3557:d
3510:d
3490:k
3470:k
3450:L
3440:L
3418:k
3392:d
3389:,
3382:c
3361:L
3341:M
3321:p
3297:p
3277:M
3257:M
3229:n
3174:M
3150:m
3147:,
3141:,
3138:1
3135:=
3132:j
3124:n
3121:,
3115:,
3112:1
3109:=
3106:i
3096:i
3092:x
3083:j
3080:i
3076:z
3055:n
3052:,
3046:,
3043:1
3040:=
3037:i
3027:i
3023:x
3019:M
3011:j
3008:i
3004:z
2998:m
2993:1
2990:=
2987:j
2962:M
2933:j
2930:i
2926:z
2905:1
2902:=
2897:i
2893:x
2872:m
2869:=
2866:M
2846:M
2826:M
2800:n
2797:,
2791:,
2788:1
2785:=
2782:i
2774:}
2771:1
2768:,
2765:0
2762:{
2754:i
2750:x
2741:m
2738:,
2732:,
2729:1
2726:=
2723:j
2715:n
2712:,
2706:,
2703:1
2700:=
2697:i
2689:}
2686:1
2683:,
2680:0
2677:{
2669:j
2666:i
2662:z
2652:n
2649:,
2643:1
2640:=
2637:i
2627:i
2623:x
2619:M
2611:j
2608:i
2604:z
2598:m
2593:1
2590:=
2587:j
2572:m
2569:,
2563:,
2560:1
2557:=
2554:j
2546:1
2543:=
2538:j
2535:i
2531:z
2525:n
2520:1
2517:=
2514:i
2491:i
2487:x
2481:i
2477:f
2471:n
2466:1
2463:=
2460:i
2452:+
2447:j
2444:i
2440:z
2434:j
2430:d
2424:j
2421:i
2417:c
2411:m
2406:1
2403:=
2400:j
2390:n
2385:1
2382:=
2379:i
2340:0
2337:=
2332:j
2329:i
2325:z
2304:i
2284:j
2264:1
2261:=
2256:j
2253:i
2249:z
2226:j
2223:i
2219:z
2193:j
2190:i
2186:y
2165:j
2145:n
2142:,
2136:,
2133:1
2130:=
2127:i
2104:+
2101:=
2096:i
2092:u
2063:i
2043:j
2023:0
2020:=
2015:j
2012:i
2008:y
1987:i
1967:0
1964:=
1959:i
1955:x
1928:n
1925:,
1919:,
1916:1
1913:=
1910:i
1902:}
1899:1
1896:,
1893:0
1890:{
1882:i
1878:x
1869:m
1866:,
1860:,
1857:1
1854:=
1851:j
1843:n
1840:,
1834:,
1831:1
1828:=
1825:i
1817:0
1809:j
1806:i
1802:y
1792:n
1789:,
1783:1
1780:=
1777:i
1767:i
1763:x
1757:i
1753:u
1744:j
1741:i
1737:y
1731:j
1727:d
1721:m
1716:1
1713:=
1710:j
1695:m
1692:,
1686:,
1683:1
1680:=
1677:j
1669:1
1666:=
1661:j
1658:i
1654:y
1648:n
1643:1
1640:=
1637:i
1614:i
1610:x
1604:i
1600:f
1594:n
1589:1
1586:=
1583:i
1575:+
1570:j
1567:i
1563:y
1557:j
1553:d
1547:j
1544:i
1540:c
1534:m
1529:1
1526:=
1523:j
1513:n
1508:1
1505:=
1502:i
1463:i
1441:j
1437:d
1416:m
1413:,
1407:,
1404:1
1401:=
1398:j
1378:n
1375:,
1369:,
1366:1
1363:=
1360:i
1338:j
1335:i
1331:y
1310:0
1307:=
1302:i
1298:x
1277:i
1257:1
1254:=
1249:i
1245:x
1224:n
1221:,
1215:,
1212:1
1209:=
1206:i
1184:i
1180:x
1151:i
1125:i
1121:u
1100:i
1078:i
1074:u
1053:m
1050:,
1044:,
1041:1
1038:=
1035:j
1015:j
993:j
989:d
968:m
965:,
959:,
956:1
953:=
950:j
930:n
927:,
921:,
918:1
915:=
912:i
892:j
872:i
850:j
847:i
843:c
822:n
819:,
813:,
810:1
807:=
804:i
784:i
762:i
758:f
737:m
717:n
697:m
677:n
655:n
623:k
619:n
609:k
601:k
589:k
585:k
571:)
566:n
562:k
558:(
555:O
535:)
532:n
529:d
524:)
519:2
510:/
506:k
497:k
494:(
491:O
487:2
483:(
480:O
430:)
425:k
420:(
417:O
413:n
389:k
379:k
346:k
336:q
332:p
326:S
321:q
314:P
309:p
302:,
300:k
295:S
278:d
273:R
260:S
241:d
236:R
223:P
190:n
164:F
160:D
156:L
109:)
103:(
98:)
94:(
84:·
77:·
70:·
63:·
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
