EUDML

Advanced Search

Currently displaying 1 – 3 of 3

Order by Relevance | Title | Year of publication

Fast approximation of minimum multicast congestion – Implementation versus theory

Andreas Baltz; Anand Srivastav — 2004

RAIRO - Operations Research - Recherche Opérationnelle

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known $N P$ -hard multicommodity flow problem. We give the presently best theoretical approximation results as well as efficient implementations. In particular we show that for a network with $m$ edges and $k$ multicast requests, an $r (1 + ε) (r t e x t O P T + exp (1) ln m)$ -approximation can be computed in $O (k m ε^{- 2} ln k ln m)$ time, where $β$ bounds the time for computing an $r$ -approximate minimum Steiner tree. Moreover, we present a new fast heuristic that...

Fast approximation of minimum multicast congestion – Implementation VERSUS Theory

Andreas Baltz; Anand Srivastav — 2010

RAIRO - Operations Research

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known -hard multicommodity flow problem. We give the presently best theoretical approximation results as well as efficient implementations. In particular we show that for a network with edges and multicast requests, an OPT + exp(1)ln)-approximation can be computed in lnln) time, where bounds the time for computing an -approximate minimum Steiner tree. Moreover, we present a new fast...

The structure of maximum subsets of ${1, \dots, n}$ with no solutions to $a + b = k c$ .

Baltz, Andreas; Hegarty, Peter; Knape, Jonas; Larsson, Urban; Schoen, Tomasz — 2005

The Electronic Journal of Combinatorics [electronic only]

Page 1

Download Results (CSV)

Advanced Search

Formula preview

Currently displaying 1 – 3 of 3

Fast approximation of minimum multicast congestion – Implementation versus theory

Fast approximation of minimum multicast congestion – Implementation VERSUS Theory

The structure of maximum subsets of { 1 , ⋯ , n } with no solutions to a + b = k c .

The structure of maximum subsets of ${1, \dots, n}$ with no solutions to $a + b = k c$ .