Abstract

Abstract: Facility Location Problems (FLPs) involve the placement of facilities in a shared environment for serving multiple customers while minimizing transportation and other costs. FLPs defined on graphs are very general and broadly applicable. Two such fundamental FLPs are the Vertex K-Center (VKC) and the Vertex K-Median (VKM) problems. Although both these problems are NP-hard, many heuristic and approximation algorithms have been developed for solving them in practice. However, state-of-the-art heuristic algorithms require the input graph G to be complete, in which the edge joining two vertices is also the shortest path between them. When G doesn't satisfy this property, these heuristic algorithms have to be invoked only after computing the metric closure of G, which in turn requires the computation of all-pairs shortest-path (APSP) distances. Existing APSP algorithms, such as the Floyd-Warshall algorithm, have a poor time complexity, making APSP computations a bottleneck for deploying the heuristic algorithms on large VKC and VKM instances. To remedy this, we propose the use of a novel algorithmic pipeline based on a graph embedding algorithm called FastMap. FastMap is a near-linear-time algorithm that embeds the vertices of G in a Euclidean space while approximately preserving the shortest-path distances as Euclidean distances for all pairs of vertices. The FastMap embedding can be used to circumvent the barrier of APSP computations, creating a very efficient pipeline for solving FLPs. On the empirical front, we provide test results that demonstrate the efficiency and effectiveness of our novel approach.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.