AG 1, AG 2, AG 3, AG 4   Info

AG Audience

-- Not specified --

45 Minutes

Saarbrücken

We consider the problem of designing a minimum cost network to allow routing a given set of flow demands to a single sink. The solution involves laying cables along some edges so that the required demands can be routed in the resulting capacitated network. The cables are selected from a finite set of available cable types which have different cost and capacity characteristics and obey the principle of economies of scale (i.e., the cost-capacity ratio is smaller for cables with higher capacity).

We present the (combinatorial) constant factor approximation algorithm of Guha, Meyerson and Munagala (FOCS 00) for a special case of the problem called Access Network Design, and the constant factor approximation algorithm of Talwar (IPCO 02), which is based on Linear Programming rounding.

Dimitris Fotakis

--email hidden

passcode not visible

logged in users only

Approximation Algorithms