Flexible allocation on related machines with assignment restrictions

DOI10.1016/J.DAM.2018.05.004MaRDI QIDQ1801074zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Flexible cell selection in cellular networks
• Flexible bandwidth assignment with application to optical networks
• Flexible Bandwidth Assignment with Application to Optical Networks
• Flexible resource allocation to interval jobs
• Distributed approximation of \(k\)-service assignment

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• A Polynomial Time Approximation Scheme for the Multiple Knapsack 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
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Distributed approximation of cellular coverage
• Flexible Bandwidth Assignment with Application to Optical Networks
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Network flows. Theory, algorithms, and applications.
• On the complexity of approximating \(k\)-set packing
• Profit maximization in flex-grid all-optical networks
• Tight approximation algorithms for maximum general assignment problems

Cited in

(3)

• Distributed approximation of \(k\)-service assignment
• Flexible cell selection in cellular networks
• Airports and railways with unsplittable demand

This page was built for publication: Flexible allocation on related machines with assignment restrictions

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