TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 11091

Packing and Scheduling Algorithms for Information and Communication Services

( Feb 27 – Mar 04, 2011 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/11091

Organizers

Contact


Summary

Packing and scheduling are one area where mathematics meets puzzles. While many of these problems stem from real-life applications, they have also been of fundamental theoretical importance. In a packing problem given is a set of items and one or more (multi-dimensional) bins. The objective is to maximize the profit from packing a subset of the items, or to minimize the cost of packing all items. In a scheduling problem, given are a set of jobs and a set of machines. One needs to schedule the jobs to run on the machines (under some constraints) so as to optimize an objective function that depends on the order of the jobs, on their completion times or on the machines by which they are processed. Storage allocation in computer networks, cutting stock problems in various industries and production planning are only few of the applications of packing and scheduling. With the growing impact of next generation technologies in information and communication services (some examples are Video-on-Demand systems, web applications and wireless networks), practitioners as well as theoreticians seek fast and efficient solutions for new variants of some classic packing and scheduling problems, which are crucial for optimizing the performance of these systems.

Since many of these problems are NP-hard, it is natural to seek efficient approximate solutions. Traditionally, such approximations are obtained by using fundamental tools from combinatorial optimization and mathematical programming. While for some of the problems there exist algorithms which achieve the best possible approximation ratio, one major effort of this community has been to close the gaps in running times between heuristic solutions, which perform well in practice, and algorithms which are provably efficient in terms of approximation ratio, but impractical in use. The large class of approximation schemes for packing and scheduling problems has been the recent target of this effort.

Parameterized complexity uses refined measures for the approximability of a given problem, by referring, e.g., to approximation with instance parameters, by defining performance functions (instead of performance ratios) and by defining the quality of approximation as parameter. Such measures provide further insight to the studied problems and lead to the design of algorithms that work efficiently if the parameters of the input instance are small (even if the size of the input is large). Efficient parameterization for packing and scheduling problems is a major challenge on the way to obtaining practical algorithms.

During the 5 days of the seminar, 24 talks were given by the participants. Five of these talks were two-hour tutorials and 60-minute survey talks on various topics: Kirk Pruhs gave an exciting tutorial on the challenges faced by designers of algorithms for green computing; Dániel Marx talked about several existing connections between approximation algorithms and fixed-parameter algorithms; Ola Svensson gave an overview of the implications and techniques of two fascinating hardness of approximation results for shops and precedence constraints scheduling; Neal Young talked about using lagrangian-relaxation algorithms to solve packing and covering problems, and Magnús Halldórsson gave an overview of recent analytic work on scheduling wireless links.

The seminar successfully brought together both experts and newcomers from the areas of packing and sequencing, combinatorial optimization, mathematical programming, and parameterized complexity, with many interesting interactions. The talks left plenty of time for discussion in the afternoon. An open problem session was held on Tuesday, and problems raised there were discussed by different groups throughout the seminar and in a research groups session on Friday. A session on current and future trends in scheduling was held on Thursday, and brought up some exciting issues relating to this area.


Participants
  • Sivan Albagli (Technion - Haifa, IL)
  • Evripidis Bampis (UPMC - Paris, FR)
  • Niv Buchbinder (Tel Aviv University, IL) [dblp]
  • Ed G. Coffman Jr. (Columbia University, US)
  • Pierre-Francois Dutot (INRIA - Grenoble, FR)
  • Leah Epstein (Haifa University, IL)
  • Lisa K. Fleischer (Dartmouth College - Hanover, US) [dblp]
  • Michael D. Grigoriadis (Rutgers University - Piscataway, US)
  • Magnús M. Halldórsson (Reykjavik University, IS) [dblp]
  • Klaus Jansen (Universität Kiel, DE) [dblp]
  • David S. Johnson (AT&T Labs Research - Florham Park, US) [dblp]
  • Howard Karloff (AT&T Labs Research - Florham Park, US)
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Samir Khuller (University of Maryland - College Park, US) [dblp]
  • Asaf Levin (Technion - Haifa, IL)
  • Alejandro Lopez-Ortiz (University of Waterloo, CA) [dblp]
  • Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Monaldo Mastrolilli (IDSIA - Manno, CH) [dblp]
  • Claire Mathieu (Brown University - Providence, US) [dblp]
  • Ernst W. Mayr (TU München, DE) [dblp]
  • Nicole Megow (TU Berlin, DE) [dblp]
  • Rolf H. Möhring (TU Berlin, DE) [dblp]
  • Seffi Naor (Technion - Haifa, IL) [dblp]
  • Kirk Pruhs (University of Pittsburgh, US) [dblp]
  • Christina Robenek (Universität Kiel, DE)
  • Adi Rosén (University of Paris VII, FR) [dblp]
  • Nicolas Schabanel (University of Paris VII, FR)
  • Baruch Schieber (IBM TJ Watson Research Center - Yorktown Heights, US)
  • Ildikó Schlotter (Budapest University of Technology & Economics, HU) [dblp]
  • Ilka Schnoor (Universität Kiel, DE)
  • Jiri Sgall (Charles University - Prague, CZ) [dblp]
  • Hadas Shachnai (Technion - Haifa, IL) [dblp]
  • Alexander Souza (HU Berlin, DE)
  • Frits C. R. Spieksma (KU Leuven, BE) [dblp]
  • Ola Svensson (EPFL - Lausanne, CH) [dblp]
  • Tami Tamir (The Interdisciplinary Center - Herzliya, IL) [dblp]
  • Rob van Stee (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
  • Prudence W. H. Wong (University of Liverpool, GB) [dblp]
  • Neal E. Young (University of California - Riverside, US)
  • Shmuel Zaks (Technion - Haifa, IL) [dblp]

Classification
  • data bases / algorithms / complexity
  • optimization / scheduling

Keywords
  • Scheduling
  • packing
  • mathematical programming
  • parameterized complexity
  • approximation algorithms