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

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

Klaus Jansen

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00829-0

zbMATH Keywords

Preemptive schedulingApproximation of separationFractional graph coloringOptimization and violation

Mathematics Subject Classification ID

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

Related Items (9)

Labeled cuts in graphs ⋮ Approximation algorithms for inventory problems with submodular or routing costs ⋮ Randomized strategies for robust combinatorial optimization with approximate separation ⋮ Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games ⋮ Approximating the least core value and least core of cooperative games with supermodular costs ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ On the complexity of bandwidth allocation in radio networks ⋮ Effective Wireless Scheduling via Hypergraph Sketches ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

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
• 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
• The round-up property of the fractional chromatic number for proper circular arc graphs

This page was built for publication: Approximate strong separation with application in fractional graph coloring and preemptive scheduling.