Domination analysis for minimum multiprocessor scheduling

DOI10.1016/J.DAM.2006.02.010MaRDI QIDQ858313zbMATHOpenAlexFDO

Authors G. Gutin, A. Yeo, T. R. Jensen

Publication date 9 January 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.02.010

zbMATH Keywords

combinatorial optimizationdomination analysisminimum multiprocessor scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• Algorithms with large domination ratio
• Domination analysis of combinatorial optimization problems.
• A characterization of optimal multiprocessor schedules and new dominance rules
• A 3/2-approximation algorithm for \(k_i\)-partitioning
• Approximating theDomatic Number

Cites work

• scientific article; zbMATH DE number 5010630 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2064409 (Why is no real title available?)
• scientific article; zbMATH DE number 2064413 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• A Remark on Stirling's Formula
• A shorter, simpler, stronger proof of the Meshalkin--Hochberg--Hirsch bounds on componentwise antichains
• Algorithms with large domination ratio
• An inequality involving multinomial probabilities
• Anti-matroids
• Balls and bins: A study in negative dependence
• Combinatorial dominance guarantees for heuristic algorithms
• Domination analysis of combinatorial optimization problems.
• Domination analysis of greedy heuristics for the frequency assignment problem.
• Domination analysis of some heuristics for the traveling salesman problem
• Generalization of Sperner’s Theorem on the Number of Subsets of a Finite Set
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• TSP heuristics: domination analysis and complexity
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Transformations of generalized ATSP into ATSP.

Cited in

(6)

• Domination analysis of combinatorial optimization problems.
• A multiparameter analysis of domino tiling with an application to concurrent systems
• Algorithms with large domination ratio
• The bilinear assignment problem: complexity and polynomially solvable special cases
• Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms

This page was built for publication: Domination analysis for minimum multiprocessor scheduling

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