ANDI: Approximation Algorithms for Network Design and Improvement

A Library for Approximation Algorithms for NP-hard Location, Network Design and Network Upgrade Problems

Introduction The design of efficient networks and the solution of location problems is one major application of algorithmic graph theory today. Unfortunately, many natural problems turn out to be NP-hard. As a consequence, it is unlikely that these problems can be solved efficiently, i.e. by polynomial time algorithms. To deal with this fact, the notion of approximation algorithm has been developed. An approximation algorithm finds a solution in polynomial time, but for the price of loss of optimality. The aim of this package is to provide efficient implementations of recent approximation algorithms for several location and network design problems. Our algorithms are compatible with the data types of LEDA, the "Library of Efficient Datatypes and Algorithms." (See http://www.mpi-sb.mpg.de/LEDA/ for details on LEDA and how to obtain a copy of LEDA.) The implementation heavily depends on LEDA, so it can not be used without it. Available Algorithms: bicriteria compact location problem on undirected graphs p-center problem on directed graphs and k-neighbor-p-center problem on undirected graphs bottleneck spanning tree problem under network node upgrade model network improvement by edge upgrade light approximate shortest path trees News 16.2.1999: release of version 1.0 (clean up of all algorithms and the documentation; many improvements) 27.10.1998: minor changes to make the library compile with gcc 2.8.1 and LEDA 3.7.1 (see note below!) 19.10.1998: minor update of the package. 17.4.1998: Some bugs have been fixed. Especially the k-neighbor p-center algorithm did strange things. 1.4.1998: The first alpha release is out and can be downloaded below. Note: On our system (Solaris) compiling with gcc 2.8.1 caused an internal compiler error. If this happens disable optimization by setting CXXFLAGS=-g. Download The library was tested on Solaris and Linux. If you have any problems or comments please contact me at wirth@informatik.uni-wuerzburg.de. The sources as tar.gz compressed package (240k) andi-1.0.tar.gz The documentation as gzipped PostScript file (100k) andi.ps.gz This software package may be freely distributed and used for private and scientific purposes. The authors refuse any warranty and liabilities. Hans-Christoph Wirth E-Mail: wirth@informatik.uni-wuerzburg.de

Zurück