Approximation algorithms and relaxations for a service provision problem on a telecommunication network

DOI10.1016/S0166-218X(02)00234-2zbMath1023.68008MaRDI QIDQ1399109

Asgeir Tomasgard, Shane Dye, Leen Stougie

Publication date: 30 July 2003

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

zbMATH Keywords

knapsack problemworst-case analysisapproximation algorithmstelecommunicationLP relaxationservice provisiondistributed processing networks

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items (2)

A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modelling aspects of distributed processing in telecommunication networks
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Feasibility in transportation networks with supply eating arcs
• Adaptive Video on Demand

This page was built for publication: Approximation algorithms and relaxations for a service provision problem on a telecommunication network