Distributed approximation of k-service assignment

DOI10.1007/S00446-017-0321-3MaRDI QIDQ1733389zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Sven Köhler, Dror Rawitz

Publication date 21 March 2019

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-017-0321-3

Mathematics Subject Classification ID

Approximation algorithms (68W25) Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Matching models (91B68)

Recommendations

• Distributed approximation of \(k\)-service assignment
• Distributed approximation of cellular coverage
• Tight approximation algorithms for maximum separable assignment problems
• The Distributedk-Server Problem—A Competitive Distributed Translator fork-Server Algorithms
• Coupled and \(k\)-sided placements: generalizing generalized assignment

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A unified approach to approximating resource allocation and scheduling
• An approximation algorithm for the generalized assignment problem
• An efficient approximation for the generalized assignment problem
• Approximate Algorithms for the 0/1 Knapsack Problem
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of network synchronization
• Distributed Computing: A Locality-Sensitive Approach
• Distributed approximation of cellular coverage
• Distributed backup placement in networks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Flexible cell selection in cellular networks
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• On Multidimensional Packing Problems
• On chromatic number of graphs and set-systems
• On the complexity of approximating \(k\)-set packing
• Online set packing
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Tight approximation algorithms for maximum general assignment problems

Cited in

(5)

• Approximation algorithms and relaxations for a service provision problem on a telecommunication network
• Distributed approximation of \(k\)-service assignment
• Distributed approximation of cellular coverage
• Distributed Approximation Algorithm for Resource Clustering
• Client assignment problems for latency minimization

This page was built for publication: Distributed approximation of \(k\)-service assignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1733389)