Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines

DOI10.1007/978-3-031-18530-4_24zbMath1528.90111OpenAlexW4312883194MaRDI QIDQ6166913

Akiyoshi Shioura, Yusuke Saito

Publication date: 3 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-18530-4_24

zbMATH Keywords

approximation algorithmparallel machine schedulingnetwork optimizationpolynomial-time approximation scheme

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)

Cites Work

• Unnamed Item
• Incremental network design with shortest paths
• Network construction problems with due dates
• A survey on offline scheduling with rejection
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Incremental network design with maximum flows
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• Network construction/restoration problems: cycles and complexity
• Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
• Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem
• Incremental Network Design with Minimum Spanning Trees
• Approximation Schemes for the Restricted Shortest Path Problem
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• Multiprocessor Scheduling with Rejection
• Approximating Incremental Combinatorial Optimization Problems
• The constrained minimum spanning tree problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

This page was built for publication: Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines