A class of greedy algorithms for the generalized assignment problem

DOI10.1016/S0166-218X(99)00224-3zbMath1064.90019OpenAlexW2034917120MaRDI QIDQ1570837

H. Edwin Romeijn, Dolores Romero Morales

Publication date: 2000

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00224-3

zbMATH Keywords

Greedy heuristicAsymptotic optimalityGeneralized Assignment ProblemAsymptotic feasibility

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (17)

An optimization-based heuristic for the machine reassignment problem ⋮ Fast machine reassignment ⋮ Lagrangian relaxation guided problem space search heuristics for generalized assignment problems ⋮ A note of reduced dimension optimization algorithm of assignment problem ⋮ Two dimensional guillotine cutting stock and scheduling problem in printing industry ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Sensitivity analysis of combinatorial optimization problems using evolutionary bilevel optimization and data mining ⋮ Connectivity and stochastic robustness of synchronized multi-drone systems ⋮ Improved Lagrangian bounds and heuristics for the generalized assignment problem ⋮ Solving the wire-harness design problem at a European car manufacturer ⋮ Heuristics for multi-item two-echelon spare parts inventory control subject to aggregate and individual service measures ⋮ Greedy approaches for a class of nonlinear generalized assignment problems ⋮ A probabilistic analysis of the multi-period single-sourcing problem ⋮ An algorithm for the generalized quadratic assignment problem ⋮ The generalized assignment problem with flexible jobs ⋮ Large-scale local search heuristics for the capacitated vertexp-center problem ⋮ Heuristic allocation based on a dynamic programming state-space representation

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic analysis of the multiknapsack value function
• Probabilistic analysis of the generalised assignment problem
• A survey of algorithms for the generalized assignment problem
• A probabilistic feasibility and value analysis of the generalized assignment problem
• A class of generalized greedy algorithms for the multi-knapsack problem
• A property of assignment type mixed integer linear programming problems
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• Two Lines Least Squares
• Multicommodity Distribution System Design by Benders Decomposition
• A branch and bound algorithm for the generalized assignment problem
• An Integer Generalized Transportation Model for Optimal Job Assignment in Computer Networks
• Modeling Facility Location Problems as Generalized Assignment Problems
• An all Zero-One Algorithm for a Certain Class of Transportation Problems
• Convex Analysis

This page was built for publication: A class of greedy algorithms for the generalized assignment problem