𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximation algorithm for Stackelberg network pricing

✍ Scribed by Sébastien Roch; Gilles Savard; Patrice Marcotte

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
182 KB
Volume
46
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Approximation algorithm for the group St
Approximation algorithm for the group Steiner network problem
✍ Michal Penn; Stas Rozenfeld 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

## Abstract In this article we study the __group Steiner network__ problem, which is defined in the following way. Given a graph __G__ = (__V,E__), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of repres

An Improved Approximation Algorithm for
An Improved Approximation Algorithm for MULTIWAY CUT
✍ Gruia Călinescu; Howard Karloff; Yuval Rabani 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 132 KB

Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due

Approximation Algorithms for Network Des
Approximation Algorithms for Network Design Problems on Bounded Subsets
✍ Dorit S. Hochbaum; Joseph (Seffi) Naor 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 141 KB

We address the problem of designing a network so that certain connectivity requirements are satisfied, at minimum cost of the edges used. The requirements are specified for each subset of vertices in terms of the number of edges with one endpoint in the set. We address a class of such problems, wher