Flexible allocation on related machines with assignment restrictions

DOI10.1016/j.dam.2018.05.004zbMath1401.90081OpenAlexW2806826029MaRDI QIDQ1801074

Dror Rawitz, Ariella Voloshin

Publication date: 26 October 2018

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

Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.004

zbMATH Keywords

approximation algorithmsLP roundinglocal ratioflexible resource allocation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Distributed approximation of cellular coverage
• An efficient approximation for the generalized assignment problem
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On the complexity of approximating \(k\)-set packing
• Profit Maximization in Flex-Grid All-Optical Networks
• Flexible Bandwidth Assignment with Application to Optical Networks
• Tight approximation algorithms for maximum general assignment problems
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A unified approach to approximating resource allocation and scheduling