Approximate strong separation with application in fractional graph coloring and preemptive scheduling.

DOI10.1016/S0304-3975(02)00829-0zbMath1044.68127MaRDI QIDQ1401329

Klaus Jansen

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Preemptive scheduling; Approximation of separation; Fractional graph coloring; Optimization and violation

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Approximation algorithms for general packing problems and their application to the multicast congestion problem, On the complexity of bandwidth allocation in radio networks

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Scheduling subject to resource constraints: Classification and complexity
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• Bin packing can be solved within 1+epsilon in linear time
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Resource constrained scheduling as generalized bin packing
• Zero knowledge and the chromatic number
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• Fractional and integral colourings
• Tight approximations for resource constrained scheduling and bin packing
• Approximation algorithms for knapsack problems with cardinality constraints
• Graph imperfection. I
• Colouring series-parallel graphs
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Bounds for Multiprocessor Scheduling with Resource Constraints
• On the hardness of approximating minimization problems