Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. An improved approximation algorithm for virtual private network design
 
conference paper

An improved approximation algorithm for virtual private network design

Eisenbrand, Friedrich  
•
Grandoni, Fabrizio
2005
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Virtual private network design deals with the reservation of capacities in a network, such that the nodes can share communication. Each node in the network has associated upper bounds on the amount of flow that it can send to the network and receive from the network respectively. The problem then is to reserve capacities at minimum cost and to compute paths between every pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. In this paper we present a simple 4.74-approximation algorithm for virtual private network design. The previous best approximation algorithm for this problem achieves a ratio of 5.55 (Gupta, Kumar, and Roughgarden STOC'03).

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

file-121632.gz.gz

Access type

openaccess

Size

44 KB

Format

Unknown

Checksum (MD5)

7e19348eebe1423c70803f1bb36c3468

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés