Tight approximations for resource constrained scheduling and bin packing
type: Item
instance of: scholarly article
title: Tight approximations for resource constrained scheduling and bin packing
zbMATH Open document ID: 0892.60013
DOI: 10.1016/S0166-218X(97)00045-0
author: Anand Srivastav
author: Peter Stangier
published in: Discrete Applied Mathematics
publication date: 1998-01-07T00:00:00Z
full work available at URL: dam
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 60E15
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 1088866
zbMATH Keywords: resource constrained scheduling
zbMATH Keywords: multidimensional bin packing
zbMATH Keywords: randomized algorithm
zbMATH Keywords: derandomization
zbMATH Keywords: approximation algorithm
zbMATH Keywords: chromatic index
MaRDI profile type: Publication
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Simulating (log c n )-wise independence in NC
cites work: Q3682518
cites work: Resource constrained scheduling as generalized bin packing
cites work: Q4198056
cites work: Geometric algorithms and combinatorial optimization
cites work: The NP-Completeness of Edge-Coloring
cites work: Approximation algorithms for scheduling unrelated parallel machines
cites work: Q3946078
cites work: Q4146667
cites work: Q3496342
cites work: The probabilistic method yields deterministic parallel algorithms
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: Q3670909
cites work: Q3481743
cites work: Q4868265
cites work: Bin packing can be solved within 1+epsilon in linear time
OpenAlex ID: W2054094480
Recommended article: Approximation Algorithms for Scheduling and Packing Problems
Recommended article: Q4723300
Recommended article: Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems
Recommended article: Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems
Recommended article: Approximation algorithms for extensible bin packing
Recommended article: A tight lower bound for optimal bin packing
Recommended article: Bounding the Running Time of Algorithms for Scheduling and Packing Problems
Recommended article: Bounding the running time of algorithms for scheduling and packing problems
description: scientific article; zbMATH DE number 1088866