Structural parameters for scheduling with assignment restrictions
From MaRDI portal
Publication:2205947
DOI10.1016/j.tcs.2020.08.015zbMath1464.90027arXiv1701.07242OpenAlexW2950663813MaRDI QIDQ2205947
Marten Maack, Klaus Jansen, Roberto Solis-Oba
Publication date: 21 October 2020
Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.07242
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)
Related Items
A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Algorithms for hierarchical and semi-partitioned parallel scheduling ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- Approximation algorithms for scheduling unrelated parallel machines
- Constraint satisfaction with bounded treewidth revisited
- Scheduling and fixed-parameter tractability
- A note on graph balancing problems with restrictions
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Bi-complement reducible graphs
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- Conjunctive-query containment and constraint satisfaction
- Parameterized complexity of machine scheduling: 15 open problems
- Structural parameters for scheduling with assignment restrictions
- Parallel machine scheduling with nested job assignment restrictions
- Scheduling meets \(n\)-fold integer programming
- A quasi-polynomial approximation for the restricted assignment problem
- Graph balancing: a special case of scheduling unrelated parallel machines
- Approximating clique-width and branch-width
- PTAS for Ordered Instances of Resource Allocation Problems
- Scheduling parallel machines with inclusive processing set restrictions
- Convex programming for scheduling unrelated parallel machines
- Complexity of Finding Embeddings in a k-Tree
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- On the Configuration-LP of the Restricted Assignment Problem
- A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
- All-norm approximation algorithms
- Santa Claus Schedules Jobs on Unrelated Machines
- Combinatorial Algorithm for Restricted Max-Min Fair Allocation
- Restricted Max-Min Fair Allocation
- On Allocating Goods to Maximize Fairness
- MaxMin allocation via degree lower-bounded arborescences
- On the Relationship Between Clique-Width and Treewidth
- Theory and Applications of Satisfiability Testing
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6-FREE GRAPHS
- Finding Branch-Decompositions and Rank-Decompositions
- An EPTAS for scheduling on unrelated machines of few different types
- Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
