Paper Info
Title
Approximating Call-Scheduling Makespan in All-Optical Networks
Abstract
We study the problem of routing and scheduling requests of limited durations in an all-optical network. The task is servicing the requests, assigning each of them a route from source to destination, a starting time and a wavelength, with restrictions on the number of available wavelengths. The goal is minimizing the overall time needed to serve all requests. We study the relationship between this problem and minimum path coloring and we show how to exploit known results on path coloring to derive approximation scheduling algorithms for meshes, trees and nearly-Eulerian, uniformly high-diameter graphs. Independently from the relationship with path coloring we propose different approximation algorithms for call scheduling in trees and in trees of rings. As a side result, we present a constant approximation algorithm for star networks. We assume for simplicity that all calls are released at time 0, however all our results hold also for arbitrary release dates at the expense of a factor 2 in the approximation ratio.
Year
DOI
Venue
2000
10.1007/3-540-40064-8_3
Workshop on Graph-Theoretic Concepts in Computer Science
Keywords
Field
DocType
approximating call-scheduling makespan,minimum path coloring,overall time,approximation scheduling algorithm,approximation ratio,constant approximation algorithm,arbitrary release date,all-optical network,all-optical networks,scheduling request,call scheduling,different approximation algorithm,scheduling algorithm
Telecommunications network,Star network,Computer science,Scheduling (computing),Distributed computing,Call duration,Approximation algorithm,Combinatorics,Mathematical optimization,Job shop scheduling,Algorithm,Path coloring,Connectivity
Conference
ISBN
Citations 
PageRank 
3-540-41183-6
0
0.34
References 
Authors
16
3
Name
Order
Citations
PageRank
Luca Becchetti194555.75
Miriam di Ianni214417.27
Alberto Marchetti-Spaccamela31584150.60