Lagrangian relaxation for the star-star concentrator location problem: Approximation algorithm and bounds

DOI10.1002/NET.3230150102zbMath0579.94031OpenAlexW2000675190MaRDI QIDQ3703812

Andranik Mirzaian

Publication date: 1985

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230150102

zbMATH Keywords

approximation algorithmlower boundsNP-completesuboptimal solutionsnetwork layoutcomputer communication network designconcentrator capacity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Related Items (23)

A Lagrangian heuristic for the capacitated plant location problem with single source constraints ⋮ Topological design of a two-level network with ring-star configuration ⋮ Efficient algorithms for the capacitated concentrator location problem ⋮ A branch-and-price algorithm for the capacitated facility location problem ⋮ Strategic design of distribution systems with economies of scale in transportation ⋮ Combined capacity planning and concentrator location in computer communications networks ⋮ Topological design of telecommunication networks --- local access design methods ⋮ Lower and upper bounds for a two-level hierarchical location problem in computer networks ⋮ A hybrid firefly-genetic algorithm for the capacitated facility location problem ⋮ The \(K\)-coverage concentrator location problem ⋮ Locating concentrators in centralized computer networks ⋮ Star \(p\)-hub median problem with modular arc capacities ⋮ Optimal design of a distributed network with a two-level hierarchical structure ⋮ Facility location models for distribution system design ⋮ Greedy random adaptive memory programming search for the capacitated clustering problem ⋮ A Lagrangean heuristic for the plant location problem with multiple facilities in the same site ⋮ Optimization of resource location in hierarchical computer networks ⋮ Hybrid fiber co-axial CATV network design with variable capacity optical network units ⋮ COLE: a new heuristic approach for fixed charge problem computational results ⋮ Models for planning capacity expansion in local access telecommunication networks ⋮ On a cost allocation problem arising from a capacitated concentrator covering problem ⋮ A comparison of heuristics and relaxations for the capacitated plant location problem ⋮ Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints

Cites Work

• An Efficient Branch and Bound Algorithm for the Warehouse Location Problem
• Unnamed Item
• Unnamed Item

This page was built for publication: Lagrangian relaxation for the star-star concentrator location problem: Approximation algorithm and bounds