Abstract
We study fundamental mathematical problems originating form the field of Network Optimization.
There are plenty of networks (e.g. electrical, communication, transportation, computer networks), whose efficiency is crucial. Typically, the geometry of the underlying problem is modeled as a graph G=(V,E) and the problem is to install elements of the constructed network in vertices and edges of G. Constructing an element incurs a certain cost which may depend on the location in G. We aim at obtaining a minimal cost network having all the required properties.
Such interesting network problems are mostly NP-hard, so it is unlikely that efficient algorithms for finding optimal solutions for these problems exist. We concentrate on efficiently finding close to optimal solutions by means of approximation algorithms.
|
An important field of network optimization problems is related to Network Design problems, where we are given a set of nodes of the graph (called terminals) that want to communicate with each other, and we need to buy some edges of the graph to connect all the terminals. Famous examples could be Steiner Tree problem, or Virtual Private Network design problems. Still, in case of economies of scale in buying capacities, the total installation cost could be modeled as a concave function: classical examples are buy-at-bulk problems or rent-or-buy problems. We concentrate on developing constant approximation algorithms for such problems and settle some important compexity issues. |
 |
|
Another field is related to Location problems: a relevant example is the Facility Location Problem, where we need to install facilities in vertices of the graph in order to service a given set of clients. Opening a facility incurs a location specific cost, servicing a client with a facility contributes a cost proportional to the client-facility distance. We studied the basic variant of the problem called metric Uncapacitated Facility Location, and the more general Connected Facility Location problem, where we also need to connect all the facilities, which incurs cost proportional to the total length of the edges used to connect them. We give constant factor approximation algorithms for both the variants. |
 |