Domination analysis for minimum multiprocessor scheduling

DOI10.1016/J.DAM.2006.02.010zbMATH Open1275.90025OpenAlexW2131489563MaRDI QIDQ858313FDOQ858313

A. Yeo, G. Gutin, 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

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

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)

Cites Work

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

Cited In (6)

• Algorithms with large domination ratio
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• 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
• A multiparameter analysis of domino tiling with an application to concurrent systems
• Domination analysis of combinatorial optimization problems.

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)