Optimal relay node placement in delay constrained wireless sensor network design

DOI10.1016/j.ejor.2013.08.031zbMath1339.90200OpenAlexW2001295286MaRDI QIDQ297218

Ashutosh Nigam, Y. K. Agarwal

Publication date: 24 June 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2013.08.031

zbMATH Keywords

projectionbranch and cutcutting plane/facetLagrangian-relaxationpolyhedral theoryrelay node placement

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• The network design problem with relays
• Facets of two Steiner arborescence polyhedra
• The Steiner tree problem with hop constraints
• The Steiner problem in distributed computing systems
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Dioïds and semirings: Links to fuzzy sets and other applications
• Modeling and solving the rooted distance-constrained minimum spanning tree problem
• Approximation schemes for node-weighted geometric Steiner tree problems
• Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Linear Programming Approach to the Cutting-Stock Problem
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Some generalizations of the steiner problem in graphs
• The node-weighted steiner tree problem
• An SST-based algorithm for the steiner problem in graphs
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• A strong lower bound for the Node Weighted Steiner Tree Problem
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems
• Design of Survivable Networks Using Three- and Four-Partition Facets
• Column Generation
• Tighter Bounds for Graph Steiner Tree Approximation
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems