Structural parameters for scheduling with assignment restrictions (Q2205947): Difference between revisions

Latest revision as of 20:46, 23 July 2024

scientific article; zbMATH DE number 6751075

Structural Parameters for Scheduling with Assignment Restrictions

Language	Label	Description	Also known as
English	Structural parameters for scheduling with assignment restrictions	scientific article; zbMATH DE number 6751075	Structural Parameters for Scheduling with Assignment Restrictions

Statements

instance of

scholarly article

0 references

title

Structural parameters for scheduling with assignment restrictions (English)

0 references

Structural Parameters for Scheduling with Assignment Restrictions (English)

0 references

0 references

0 references

0 references

Theoretical Computer Science

0 references

Lecture Notes in Computer Science

0 references

publication date

21 October 2020

0 references

21 July 2017

0 references

full work available at URL

https://arxiv.org/abs/1701.07242

0 references

zbMATH Keywords

scheduling

0 references

approximation

0 references

approximation scheme

0 references

FPT algorithm

0 references

treewidth

0 references

cliquewidth

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Theory and Applications of Satisfiability Testing

0 references

Constraint satisfaction with bounded treewidth revisited

0 references

Approximation algorithms for scheduling unrelated parallel machines

0 references

Exact and Approximate Algorithms for Scheduling Nonidentical Processors

0 references

Graph balancing: a special case of scheduling unrelated parallel machines

0 references

A note on graph balancing problems with restrictions

0 references

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

0 references

Scheduling parallel machines with inclusive processing set restrictions

0 references

Parallel machine scheduling with nested job assignment restrictions

0 references

Scheduling and fixed-parameter tractability

0 references

Q3012402

0 references

Q2816090

0 references

Structural parameters for scheduling with assignment restrictions

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

Complexity of Finding Embeddings in a <i>k</i>-Tree

0 references

Finding Branch-Decompositions and Rank-Decompositions

0 references

Conjunctive-query containment and constraint satisfaction

0 references

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

0 references

Convex programming for scheduling unrelated parallel machines

0 references

All-norm approximation algorithms

0 references

MaxMin allocation via degree lower-bounded arborescences

0 references

On Allocating Goods to Maximize Fairness

0 references

Q4636620

0 references

Restricted Max-Min Fair Allocation

0 references

On the Relationship Between Clique-Width and Treewidth

0 references

Bi-complement reducible graphs

0 references

LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P<sub>6</sub>-FREE GRAPHS

0 references

Q5503435

0 references

A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges

0 references

On the Configuration-LP of the Restricted Assignment Problem

0 references

A quasi-polynomial approximation for the restricted assignment problem

0 references

Q5091233

0 references

PTAS for Ordered Instances of Resource Allocation Problems

0 references

Treewidth. Computations and approximations

0 references

Scheduling meets \(n\)-fold integer programming

0 references

An EPTAS for scheduling on unrelated machines of few different types

0 references

Parameterized complexity of machine scheduling: 15 open problems

0 references

Approximating clique-width and branch-width

0 references

Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments

0 references

Santa Claus Schedules Jobs on Unrelated Machines

0 references

A polynomial-time approximation scheme for maximizing the minimum machine completion time

0 references

When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

0 references

Identifiers

zbMATH Open document ID

1464.90027

0 references

1486.90093

0 references

DOI

10.1016/j.tcs.2020.08.015

0 references

10.1007/978-3-319-57586-5_30

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2205947

@@ Property / cites work @@
+Combinatorial Algorithm for Restricted Max-Min Fair Allocation
+Normal rank
@@ Property / cites work @@
+Convex programming for scheduling unrelated parallel machines
+Normal rank
@@ Property / cites work @@
+All-norm approximation algorithms
@@ Property / cites work: All-norm approximation algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+MaxMin allocation via degree lower-bounded arborescences
+Normal rank
@@ Property / cites work @@
+On Allocating Goods to Maximize Fairness
@@ Property / cites work: On Allocating Goods to Maximize Fairness / rank @@
+Normal rank
@@ Property / cites work @@
+Q4636620
@@ Property / cites work: Q4636620 / rank @@
+Normal rank
@@ Property / cites work @@
+Restricted Max-Min Fair Allocation
@@ Property / cites work: Restricted Max-Min Fair Allocation / rank @@
+Normal rank
@@ Property / cites work @@
+On the Relationship Between Clique-Width and Treewidth
+Normal rank
@@ Property / cites work @@
+Bi-complement reducible graphs
@@ Property / cites work: Bi-complement reducible graphs / rank @@
+Normal rank
@@ Property / cites work @@
+LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P<sub>6</sub>-FREE GRAPHS
+Normal rank
@@ Property / cites work @@
+Q5503435
@@ Property / cites work: Q5503435 / rank @@
+Normal rank
@@ Property / cites work @@
+A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
+Normal rank
@@ Property / cites work @@
+On the Configuration-LP of the Restricted Assignment Problem
+Normal rank
@@ Property / cites work @@
+A quasi-polynomial approximation for the restricted assignment problem
+Normal rank
@@ Property / cites work @@
+Q5091233
@@ Property / cites work: Q5091233 / rank @@
+Normal rank
@@ Property / cites work @@
+PTAS for Ordered Instances of Resource Allocation Problems
+Normal rank
@@ Property / cites work @@
+Treewidth. Computations and approximations
@@ Property / cites work: Treewidth. Computations and approximations / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling meets \(n\)-fold integer programming
@@ Property / cites work: Scheduling meets \(n\)-fold integer programming / rank @@
+Normal rank
@@ Property / cites work @@
+An EPTAS for scheduling on unrelated machines of few different types
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of machine scheduling: 15 open problems
+Normal rank
@@ Property / cites work @@
+Approximating clique-width and branch-width
@@ Property / cites work: Approximating clique-width and branch-width / rank @@
+Normal rank
@@ Property / cites work @@
+Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
+Normal rank
@@ Property / cites work @@
+Santa Claus Schedules Jobs on Unrelated Machines
@@ Property / cites work: Santa Claus Schedules Jobs on Unrelated Machines / rank @@
+Normal rank
@@ Property / cites work @@
+A polynomial-time approximation scheme for maximizing the minimum machine completion time
+Normal rank
@@ Property / cites work @@
+When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
+Normal rank