1-center problem

1-center problem

The 1-center problem or minimax or minmax location problem is a classical combinatorial optimization problem in operations research of facilities location type. In its most general case the problem is stated as follows: given a set of n demand points, a space of feasible locations of a facility and a function to calculate the transportation cost between a facility and any demand point, find a location of the facility which minimizes the maximum facility-demand point transportation cost.

The simple special case when the feasible locations and demand points are in the plane with Euclidean distance as transportation cost (planar minmax Euclidean facility location problem, Euclidean 1-center problem in the plane, etc.), it is also known as the smallest circle problem. Its generalization to n-dimensional Euclidean spaces is known as the smallest enclosing ball problem. A further generalization (weighted Euclidean facility location) is when the set of weights is assigned to demand points and the transportation cost is the sum of the products of distances by the corresponding weights.

There are numerous particular cases of the problem, depending on the choice of the locations both of demand points and facilities, as well as the distance function.

See also

  • Minsum facility location (1-median problem), with geometric median being a special case
  • Maxmin facility location (obnoxious facility location)
  • k-center problem
  • k-median problem

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Problem gambling — Classification and external resources ICD 10 F63.0 ICD 9 312.31 …   Wikipedia

  • Problem-oriented policing — (POP), coined by University of Wisconsin Madison professor Herman Goldstein, is a policing strategy that involves the identification and analysis of specific crime and disorder problems, in order to develop effective response strategies in… …   Wikipedia

  • Center Parcs — [The spelling Center Parcs , the official name, is incorrect in every language. In British English, spelling rules prescribe Centre Parks , in American English Center Parks (see spelling differences), and in French Centre Parcs .] is a European… …   Wikipedia

  • center — n Center, middle, midst, core, hub, focus, nucleus, heart are comparable when meaning the point, spot, or portion of a thing which is comparable to a point around which a circle is described. Center approximates more or less closely its strict… …   New Dictionary of Synonyms

  • Center for Science in the Public Interest — Abbreviation CSPI Formation 1971 Type Non profit …   Wikipedia

  • Center for Digital Inclusion — Founder(s) Rodrigo Baggio Type Non profit Organization Founded 1995 (1995) …   Wikipedia

  • Problem of Apollonius — In Euclidean plane geometry, Apollonius problem is to construct circles that are tangent to three given circles in a plane (Figure 1); two circles are tangent if they touch at a single point. Apollonius of Perga (ca. 262 BC ndash; ca. 190 BC)… …   Wikipedia

  • Center for Court Innovation — The Center for Court Innovation is a non profit think tank headquartered in New York that helps courts and criminal justice agencies aid victims, reduce crime and improve public trust in justice. [cite web|url=http://www.courtinnovation.org/… …   Wikipedia

  • Center for Minority Health — The Center for Minority Health (CMH), part of The University of Pittsburgh Graduate School of Public Health, was established in 1994 through a grant from the Richard King Mellon Foundation. It provides the framework that is necessary to address… …   Wikipedia

  • Center of mass — In physics, the center of mass of a system of particles is a specific point at which, for many purposes, the system s mass behaves as if it were concentrated. The center of mass is a function only of the positions and masses of the particles that …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”