Moderate exponential-time algorithms for scheduling problems
From MaRDI portal
Publication:2095519
DOI10.1007/s10288-022-00525-1OpenAlexW4308313553WikidataQ115605836 ScholiaQ115605836MaRDI QIDQ2095519
Mathieu Liedloff, Vincent T'kindt, Frederico Della Croce
Publication date: 17 November 2022
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10288-022-00525-1
Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Deterministic scheduling theory in operations research (90B35) General topics in the theory of algorithms (68W01)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On an extension of the Sort \& Search method with application to scheduling theory
- Exact exponential algorithms.
- A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
- New algorithms for minimizing the weighted number of tardy jobs on a single machine
- Scheduling and fixed-parameter tractability
- Dynamic programming meets the principle of inclusion and exclusion
- A note on the complexity of the chromatic number problem
- Approximability of flow shop scheduling
- Makespan minimization in open shops: A polynomial time approximation scheme
- Decomposition of the single machine total tardiness problem
- Which problems have strongly exponential complexity?
- Time-approximation trade-offs for inapproximable problems
- Exact exponential algorithms for 3-machine flowshop scheduling problems
- Parameterized complexity of machine scheduling: 15 open problems
- An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
- Exact algorithms for maximum independent set
- \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- Combinatorial \(n\)-fold integer programming and applications
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- Parameterized complexity of a coupled-task scheduling problem
- Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
- Scheduling meets \(n\)-fold integer programming
- On subexponential and FPT-time inapproximability
- Optimal two- and three-stage production schedules with setup times included
- Enumeration of Pareto Optima for a Flowshop Scheduling Problem with Two Criteria
- Scheduling Partially Ordered Jobs Faster Than 2 n
- A measure & conquer approach for the analysis of exact algorithms
- The Travelling Salesman Problem in Bounded Degree Graphs
- Set Partitioning via Inclusion-Exclusion
- An Improved Exact Algorithm for Cubic Graph TSP
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- Computing Partitions with Applications to the Knapsack Problem
- Finding a Maximum Independent Set
- Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
- On Problems as Hard as CNF-SAT
- Parameterized and Exact Computation
- Determinant Sums for Undirected Hamiltonicity
- 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- When polynomial approximation meets exact computation
- Scheduling
- On the complexity of \(k\)-SAT
- Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
This page was built for publication: Moderate exponential-time algorithms for scheduling problems
