Moderate exponential-time algorithms for scheduling problems
From MaRDI portal
Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites work
- scientific article; zbMATH DE number 3550186 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- 3-SAT faster and simpler -- unique-SAT bounds for PPSZ hold in general
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- A Computing Procedure for Quantification Theory
- A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
- A machine program for theorem-proving
- A measure \& conquer approach for the analysis of exact algorithms
- A note on the complexity of the chromatic number problem
- An Improved Exact Algorithm for Cubic Graph TSP
- An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
- Approximability of flow shop scheduling
- Combinatorial \(n\)-fold integer programming and applications
- Computing Partitions with Applications to the Knapsack Problem
- Decomposition of the single machine total tardiness problem
- Determinant sums for undirected Hamiltonicity
- Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
- Dynamic programming meets the principle of inclusion and exclusion
- Enumeration of Pareto optima for a flowshop scheduling problem with two criteria
- Exact algorithms for maximum independent set
- Exact exponential algorithms for 3-machine flowshop scheduling problems
- Exact exponential algorithms.
- Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
- Finding a Maximum Independent Set
- Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
- Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
- Makespan minimization in open shops: A polynomial time approximation scheme
- Moderate exponential-time algorithms for scheduling problems
- Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion
- Multicriteria scheduling. Theory, models and algorithms. Translated from the French by Henry Scott.
- New algorithms for minimizing the weighted number of tardy jobs on a single machine
- On an extension of the Sort \& Search method with application to scheduling theory
- On problems as hard as CNF-SAT
- On subexponential and FPT-time inapproximability
- On the complexity of \(k\)-SAT
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- On the parameterized complexity of interval scheduling with eligible machine sets
- Optimal two- and three-stage production schedules with set-up time included
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- Parameterized and Exact Computation
- Parameterized complexity of a coupled-task scheduling problem
- Parameterized complexity of machine scheduling: 15 open problems
- Scheduling algorithms
- Scheduling and fixed-parameter tractability
- Scheduling meets n-fold integer programming
- Scheduling partially ordered jobs faster than \(2^{n }\)
- Scheduling. Theory, algorithms, and systems
- Set partitioning via inclusion-exclusion
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- The Travelling Salesman Problem in Bounded Degree Graphs
- Time-approximation trade-offs for inapproximable problems
- When polynomial approximation meets exact computation
- Which problems have strongly exponential complexity?
- \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
This page was built for publication: Moderate exponential-time algorithms for scheduling problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030968)
