scientific article

zbMATH Open0772.68043MaRDI QIDQ4036610FDOQ4036610

Philip N. Klein, R. Ravi, Ajit Agrawal

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

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
• scientific article; zbMATH DE number 1754642

zbMATH Keywords

combinatorial optimizationsingle-processor schedulinginterval graph completionpolyomial time approximation algorithms

Mathematics Subject Classification ID

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

Cited In (15)

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

This page was built for publication:

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