Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
type: Item
instance of: scholarly article
title: Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
zbMATH Open document ID: 1044.68127
DOI: 10.1016/S0304-3975(02)00829-0
author: Klaus Jansen
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1965346
zbMATH Keywords: Approximation of separation
zbMATH Keywords: Optimization and violation
zbMATH Keywords: Fractional graph coloring
zbMATH Keywords: Preemptive scheduling
describes a project that uses: Knapsack
MaRDI profile type: Publication
cites work: Q3821925
cites work: Q4380372
cites work: Scheduling subject to resource constraints: Classification and complexity
cites work: Approximation algorithms for knapsack problems with cardinality constraints
cites work: Q4535060
cites work: Q4252288
cites work: Bin packing can be solved within 1+epsilon in linear time
cites work: Polynomial-time approximation schemes for geometric graphs
cites work: Zero knowledge and the chromatic number
cites work: Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
cites work: Bounds for Multiprocessor Scheduling with Resource Constraints
cites work: Resource constrained scheduling as generalized bin packing
cites work: Graph imperfection. I
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Geometric algorithms and combinatorial optimization
cites work: Q4411391
cites work: Linear-Time approximation schemes for scheduling malleable parallel tasks
cites work: Q4472514
cites work: Q4536380
cites work: Q4737537
cites work: Fractional and integral colourings
cites work: Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
cites work: On the hardness of approximating minimization problems
cites work: Q4504025
cites work: The round-up property of the fractional chromatic number for proper circular arc graphs
cites work: A fully polynomial approximation algorithm for the 0-1 knapsack problem
cites work: Q4382863
cites work: Colouring series-parallel graphs
cites work: Q4868265
cites work: Tight approximations for resource constrained scheduling and bin packing
full work available at URL: s0304-3975(02)00829-0
OpenAlex ID: W2051020376
description: scientific article; zbMATH DE number 1965346