On the optimality of exact and approximation algorithms for scheduling problems
type: Item
instance of: scholarly article
title: On the optimality of exact and approximation algorithms for scheduling problems
zbMATH Open document ID: 1393.68056
author: Lin Chen
author: Klaus Jansen
author: Guochuan Zhang
published in: Journal of Computer and System Sciences
publication date: 2018-06-06T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 6881613
zbMATH Keywords: approximation schemes
zbMATH Keywords: scheduling
zbMATH Keywords: lower bounds
zbMATH Keywords: exponential time hypothesis
MaRDI profile type: Publication
full work available at URL: j.jcss.2018.03.005
OpenAlex ID: W2800754909
cites work: Approximation schemes for scheduling on parallel machines
cites work: Minimum Makespan Scheduling with Low Rank Processing Times
cites work: On the computational hardness based on linear fpt-reductions
cites work: An improved lower bound for rank four scheduling
cites work: Q4636620
cites work: Q4503944
cites work: Q4198056
cites work: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
cites work: Exact and Approximate Algorithms for Scheduling Nonidentical Processors
cites work: Which problems have strongly exponential complexity?
cites work: An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
cites work: Bounding the Running Time of Algorithms for Scheduling and Packing Problems
cites work: Q4598212
cites work: Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
cites work: There is no EPTAS for two-dimensional knapsack
cites work: Approximation algorithms for scheduling unrelated parallel machines
cites work: On an extension of the Sort \& Search method with application to scheduling theory
cites work: Q4904144
cites work: Scheduling and fixed-parameter tractability
cites work: Q5417690
cites work: A simplified NP-complete satisfiability problem
DOI: 10.1016/J.JCSS.2018.03.005
description: scientific article; zbMATH DE number 6881613