TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2010

COGA 5-Wheel

Page Content

to Navigation

Preprints 2010

Throughput maximization for periodic packet scheduling
Citation key Report-013-2010
Author Britta Peis and Andreas Wiese
Year 2010
Number 013
Institution Technische Universität Berlin, Institut für Mathematik
Abstract In the periodic packet routing problem a number of tasks periodically create packets which have to be transported through a network. Due to capacity constraints on the edges, it might not be possible to find a schedule which delivers all packets of all tasks in a feasible way. In this case one aims to find a feasible schedule for as many tasks as possible, or, if weights on the tasks are given, for a subset of tasks of maximal weight. In this paper we investigate this problem on trees and grids with row-column paths. We distinguish between direct schedules (i.e., schedules in which each packet is delayed only in its start vertex) and not necessarily direct schedules. For these settings we present constant factor approximation algorithms, separately for the weighted and the cardinality case. Abstract. Our results combine discrete optimization with real-time scheduling. We use new techniques which are specially designed for our problem as well as novel adaptions of existing methods.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe