Domination analysis of greedy heuristics for the frequency assignment problem.

DOI10.1016/j.disc.2003.05.008zbMath1077.90081OpenAlexW2019692026MaRDI QIDQ1420614

A. E. Koller, Steven D. Noble

Publication date: 2 February 2004

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

Full work available at URL: http://bura.brunel.ac.uk/handle/2438/1674

zbMATH Keywords

Greedy heuristicDomination numberFrequency assignment problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Domination analysis for minimum multiprocessor scheduling ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Domination analysis of combinatorial optimization problems. ⋮ 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 ⋮ Dominance guarantees for above-average solutions ⋮ Models and solution techniques for frequency assignment problems ⋮ Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem

Uses Software

• CALMA

Cites Work

• Unnamed Item
• Unnamed Item
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• Frequency assignment in cellular phone networks
• TSP heuristics: domination analysis and complexity
• Lower bounds for fixed spectrum frequency assignment
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• The traveling salesman problem: new polynomial approximation algorithms and domination analysis
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Models and solution techniques for frequency assignment problems

This page was built for publication: Domination analysis of greedy heuristics for the frequency assignment problem.