Metric k-center

Metric k-center

In graph theory, the metric k-center, is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the distance of the farthest city from its closest warehouse. In graph theory this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, or in other words a complete graph that satisfies the triangle inequality.

Contents

Formal definition

Given a complete undirected graph G = (VE) with distances d(vivj) ∈ N satisfying the triangle inequality, find a subset S ⊆ V with |S| = k while minimizing:

\max_{v \in V} \min_{s \in S} d(v,s)

Computational complexity

If we sort the edges in nondecreasing order of the distances: d(e1) ≤ d(e2) ≤ … ≤ d(em) and let Gi = (ViEi), where Ei = {e1e2, …, ei}. The k-center problem is equivalent to finding the smallest index i such that Gi has a dominating set of size at most k.[1] Dominating set is NP-complete and therefore the k-center problem is also NP-complete.

Approximations

A simple greedy approximation algorithm that achieves an approximation factor of 2 builds S in k iterations. The first iteration chooses an arbitrary vertex and adds it to S. Each subsequent iteration chooses a vertex v for which d(S, v) is maximized and adds v to S. The running time of the algorithm is O(nk).[2]

Another algorithm with the same approximation factor takes advantage of the fact that the k-center problem is equivalent to finding the smallest index i such that Gi has a dominating set of size at most k and computes a maximal independent set on the of Gi, looking for the smallest index i that has a maximal independent set with a size of at least k.[3]

It is not possible to find an approximation algorithm with an approximation factor of 2 − ε for any ε > 0.[4] Furthermore, the distances of all edges in G must satisfy the triangle inequality if the k-center problem is to be approximated unless P = NP.[5]

See also

Notes

  1. ^ Vazirani 2003, pp. 47–48.
  2. ^ Gonzalez 1985, pp. 293–306.
  3. ^ Hochbaum & Shmoys 1986, pp. 533–550.
  4. ^ Hochbaum 1997, pp. 346–398.
  5. ^ Crescenzi et al. 2000.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Metric expansion of space — Physical cosmology Universe · Big Bang …   Wikipedia

  • Center of population — with a mean distance of convert|5000|km|sigfig=1|sp=us. Its antipodal point is correspondingly the farthest point from everyone on earth, and is located in the South Pacific near 15000|km|sp=us.In demographics, the center of population of a… …   Wikipedia

  • Glossary of Riemannian and metric geometry — This is a glossary of some terms used in Riemannian geometry and metric geometry mdash; it doesn t cover the terminology of differential topology. The following articles may also be useful. These either contain specialised vocabulary or provide… …   Wikipedia

  • Poincaré metric — In mathematics, the Poincaré metric, named after Henri Poincaré, is the metric tensor describing a two dimensional surface of constant negative curvature. It is the natural metric commonly used in a variety of calculations in hyperbolic geometry… …   Wikipedia

  • Goal Question Metric — (GQM) ist eine systematische Vorgehensweise zur Erstellung spezifischer Qualitätsmodelle im Bereich der Softwareentwicklung. Diese lässt sich als Baumstruktur darstellen. Als Wurzel steht das Ziel (Goal), das über die Knoten (Questions) zu den… …   Deutsch Wikipedia

  • Fernald Feed Materials Production Center — The Fernald Feed Materials Production Center (commonly referred to simply as Fernald) was a uranium processing facility located near the rural town of Fernald, in Hamilton County, Ohio, about 20 miles northwest of Cincinnati, which fabricated… …   Wikipedia

  • Kerr metric — In general relativity, the Kerr metric (or Kerr vacuum) describes the geometry of spacetime around a rotating massive body. According to this metric, such rotating bodies should exhibit frame dragging, an unusual prediction of general relativity; …   Wikipedia

  • Data & Analysis Center for Software — The Data Analysis Center for Software (DACS) is one of several United States Department of Defense (DoD) sponsored Information Analysis Centers (IACs), administered by the Defense Technical Information Center (DTIC). It is technically managed by… …   Wikipedia

  • University Medical Center of Southern Nevada — Infobox Hospital Name = University Medical Center of Southern Nevada Org/Group = Caption = map type = latitude = longitude = Location = Las Vegas Region = Clark County State = Nevada Country = US Coordinates = HealthCare = Public Type = Teaching… …   Wikipedia

  • Valley Hospital Medical Center Heliport — Infobox Airport name = Valley Hospital Medical Center Heliport nativename = nativename a = nativename r = image width = caption = IATA = ICAO = FAA = NV53 type = Heliport owner = operator = Valley Hospital Medical Center city served = location =… …   Wikipedia

Share the article and excerpts

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