Name
Abstract | ||
|---|---|---|
In the problem of Online Call Admission in Optical Networks, briefly called oca, we are given a graph G=(V,E) together with a set of wavelengths W (χ:=|W|) and a finite sequence σ=r1,r2,... of calls which arrive in an online fashion. Each call rj specifies a pair of nodes to be connected. A lightpath is a path in G together with a wavelength λ ∈ W. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide a lightpath to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. The objective in oca is to maximize the overall profit, that is, the number of accepted calls. A result by Awerbuch et al. states that a c-competitive algorithm for oca with one wavelength, i.e., χ:=|W|=1, implies a (c+1)-competitive algorithm for general numbers of wavelengths. However, for instance, for the line with n+1 nodes, a lower bound of n for the competitive ratio of deterministic algorithms for χ=1 makes this result void in many cases. We provide a deterministic competitive algorithm for χ1 wavelengths which achieves a competitive ratio of $\chi(\sqrt[\chi]{n} + 2)$ on the line with n+1 nodes. As long as χ1 is fixed, this is the first competitive ratio which is sublinear in n+1, the number of nodes. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11671411_15 | WAOA |
Keywords | Field | DocType |
competitive algorithm,online algorithm,deterministic algorithm,competitive ratio,call rj,accepted call,wavelength conflict constraint,deterministic competitive algorithm,c-competitive algorithm,different wavelength,deterministic online optical call,lower bound,profitability | Sublinear function,Online algorithm,Approximation algorithm,Combinatorics,Telecommunications network,Finite sequence,Computer science,Upper and lower bounds,Deterministic system (philosophy),Competitive analysis | Conference |
Volume | ISSN | ISBN |
3879 | 0302-9743 | 3-540-32207-8 |
Citations | PageRank | References |
1 | 0.35 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elisabeth Gassner | 1 | 159 | 11.92 |
| Sven O. Krumke | 2 | 308 | 36.62 |