Ordering problems approximated: Single-processor scheduling and interval graph completion

DOI10.1007/3-540-54233-7_180MaRDI QIDQ4036610zbMATH OpenFDO

Authors R. Ravi, Ajit Agrawal, Philip N. Klein

Publication date 18 May 1993

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

Full work available at URL https://doi.org/10.1007/3-540-54233-7_180

zbMATH Keywords

combinatorial optimizationinterval graph completionpolyomial time approximation algorithmssingle-processor scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• On the approximability of single-machine scheduling with precedence constraints
• On the approximability of average completion time scheduling under precedence constraints.
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• On the approximability of average completion time scheduling under precedence constraints

Cited in

(20)

• Parameterized algorithmics for linear arrangement problems
• Improved exact approaches for row layout problems with departments of equal length
• On the approximability of an interval scheduling problem
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Node set optimization problem for complete Josephus cubes
• Minimum fill-in: inapproximability and almost tight lower bounds
• Designing PTASs for MIN-SUM scheduling problems
• On the interval completion of chordal graphs
• Minimum linear arrangement of chord graphs
• A branch and bound algorithm for the minimum storage-time sequencing problem
• On a binary distance model for the minimum linear arrangement problem
• An optimal time algorithm for minimum linear arrangement of chord graphs
• Experiments on the minimum linear arrangement problem
• Minimum flow time graph ordering.
• Complexity classification of some edge modification problems
• Multi-armed bandit for the cyclic minimum sitting arrangement problem
• Exact and heuristic computation of the scanwidth of directed acyclic graphs
• A probabilistic algorithm for optimal linear arrangements
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• Minimal cutwidth linear arrangements of abelian Cayley graphs

This page was built for publication: Ordering problems approximated: Single-processor scheduling and interval graph completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036610)