Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: Algorithmica

Search In Journal Title:

Abbravation: Algorithmica

Search In Journal Abbravation:

Publisher

Springer-Verlag

Search In Publisher:

DOI

10.1002/asna.18981471101

Search In DOI:

ISSN

1432-0541

Search In ISSN:
Search In Title Of Papers:

Approximation Algorithms for Scheduling with Reser

Authors: Florian Diedrich Klaus Jansen Fanny Pascual Denis Trystram
Publish Date: 2009/01/21
Volume: 58, Issue: 2, Pages: 391-404
PDF Link

Abstract

We study the problem of nonpreemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations where m is constant This setting is practically relevant because for various reasons some machines may not be available during specified time intervals The objective is to minimize the makespan C max which is the maximum completion timeThe general case of the problem is inapproximable unless mathsf P=mathsf NP hence we study a suitable strongly mathsf NP hard restriction namely the case where at least one machine is always available For this setting we contribute approximation schemes complemented by inapproximability results The approach is based on algorithms for multiple subset sum problems our technique yields a PTAS which is best possible in the sense that an FPTAS is ruled out unless mathsf P=mathsf NP The PTAS presented here is the first one for the problem under consideration so far not even for wellknown special cases approximation schemes have been proposed Furthermore we derive a low cost algorithm with a constant approximation ratio and discuss FPTASes for special cases as well as the complexity of the problem if m is part of the inputF Diedrich’s research was supported in part by a grant “DAAD Doktorandenstipendium” of the German Academic Exchange Service and in part by EU research project AEOLUS Algorithmic Principles for Building Efficient Overlay Computers EU contract number 015964 Part of this work done while visiting the LIG Grenoble University Supported in part by DFG priority program 1126 “Algorithmics of Large and Complex Networks” furthermore supported in part by a PPP funding “Scheduling in Communication Networks” D/05/06936 granted by the DAAD


Keywords:

References


.
Search In Abstract Of Papers:
Other Papers In This Journal:

  1. On Minimum Sum of Radii and Diameters Clustering
  2. Integer Representation and Counting in the Bit Probe Model
  3. An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization
  4. New Approximation Algorithms for Minimum Cycle Bases of Graphs
  5. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
  6. Aligning Two Convex Figures to Minimize Area or Perimeter
  7. Introduction for S.I. AofA14
  8. Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness
  9. Detecting Regular Visit Patterns
  10. Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
  11. Random Matrices and Codes for the Erasure Channel
  12. On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs
  13. The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
  14. Optimal Parallel Quantum Query Algorithms
  15. Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges
  16. Maximum Series-Parallel Subgraph
  17. A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
  18. Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
  19. The Parameterized Complexity of Local Search for TSP, More Refined
  20. Approximating Fixation Probabilities in the Generalized Moran Process
  21. Algorithms for the Homogeneous Set Sandwich Problem
  22. A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
  23. Computing Minimum Cuts by Randomized Search Heuristics
  24. Constructing Labeling Schemes through Universal Matrices
  25. An Approximation Algorithm for the Minimum Co-Path Set Problem
  26. Scheduling with an Orthogonal Resource Constraint
  27. Approximate Boyer-Moore String Matching for Small Alphabets
  28. Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
  29. Between Treewidth and Clique-Width
  30. What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
  31. Multi-sided Boundary Labeling
  32. A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs

Search Result: