Simultaneous approximation for scheduling problems

Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment, we introduce in this paper the concepts of strong simultaneous approximation ratio (SAR) and weak simultaneous approximation ratio (WAR). Then we study the two parameters under various scheduling environments, such as, non-preemptive, preemptive or fractional scheduling on identical, related or unrelated machines.

• Publication year

  2013

• Venue

  arXiv.org

• Publication date

  2013-04-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1304.4073
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximate majorization and fair online load balancing

  2001cited by this paper
• Using approximate majorization to characterize protocol fairness

  2001influential reference
• Combining fairness with throughput: online routing with multiple objectives

  2000cited by this paper
• Fairness measures for resource allocation

  2000cited by this paper
• Fairness in routing and load balancing

  1999cited by this paper
• The exact LPT-bound for maximizing the minimum completion time

  1992cited by this paper
• SCHEDULING TO MAXIMIZE THE MINIMUM PROCESSOR FINISH TIME IN A MULTIPROCESSOR SYSTEM

  1982cited by this paper
• Bounds on Multiprocessing Timing Anomalies

  1969cited by this paper
• Bounds for certain multiprocessing anomalies

  1966cited by this paper

• No citing papers are available for this paper.