On approximating a scheduling problem

DOI10.1023/A:1011441109660MaRDI QIDQ5952318zbMATH OpenOpenAlexFDO

Authors Pilu Crescenzi, Xiaotie Deng, Christos Papadimitriou

Publication date 2001

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1011441109660

zbMATH Keywords

bipartite graphcommunicationedge coloringparallel computation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication networks in operations research (90B18) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 1560337
• An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications
• Approximation algorithms for general parallel task scheduling
• Scheduling in the presence of processor networks : complexity and approximation
• Task Scheduling in Networks

Cited in

(28)

• Approximate solution of a resource-constrained scheduling problem
• On the complexity of scheduling tasks with discrete starting times
• Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns
• On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems.
• Extending Graham's result on scheduling to other heuristics
• Scheduling in switching networks with set-up delays
• Approximation of the supply scheduling problem
• Efficient approximation schemes for scheduling problems with release dates and delivery times
• A survey of methods for the solution of problems of scheduling theory
• An experimental study of LP-based approximation algorithms for scheduling problems
• scientific article; zbMATH DE number 444983 (Why is no real title available?)
• Approximation Algorithms for the Assembly Line Crew Scheduling Problem
• On the Maximum Edge Coloring Problem
• scientific article; zbMATH DE number 3941253 (Why is no real title available?)
• scientific article; zbMATH DE number 3978803 (Why is no real title available?)
• scientific article; zbMATH DE number 4029243 (Why is no real title available?)
• scientific article; zbMATH DE number 4031379 (Why is no real title available?)
• scientific article; zbMATH DE number 1560337 (Why is no real title available?)
• On Approximation Algorithms for Two-Stage Scheduling Problems
• scientific article; zbMATH DE number 850325 (Why is no real title available?)
• Approximately Supermodular Scheduling Subject to Matroid Constraints
• scientific article; zbMATH DE number 7267489 (Why is no real title available?)
• Approximation algorithms for scheduling with reservations
• On the max-weight edge coloring problem
• Buffer management for colored packets with deadlines
• Isomorphic scheduling problems
• Scheduling and fixed-parameter tractability
• Approximating the max-edge-coloring problem

This page was built for publication: On approximating a scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5952318)