Advanced

Resource allocation with wobbly functions

Andersson, A; Carlsson, Per LU and Ygge, F (2002) In Computational Optimization and Applications 23(2). p.171-200
Abstract
We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximisation version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with functions that are not necessarily concave is difficult. In this article, we focus on a large class of problem instances, with objective functions that are close to a concave function or some other smooth function, but with small irregularities in their shape. It is described that these properties are important in many practical situations. The irregularities make it hard or impossible to use known, efficient resource allocation techniques. We show... (More)
We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximisation version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with functions that are not necessarily concave is difficult. In this article, we focus on a large class of problem instances, with objective functions that are close to a concave function or some other smooth function, but with small irregularities in their shape. It is described that these properties are important in many practical situations. The irregularities make it hard or impossible to use known, efficient resource allocation techniques. We show that, for this class of functions the optimal solution can be computed efficiently. We support our claims by experimental evidence. Our experiments show that our algorithm in hard and practically relevant cases runs up to 40-60 times faster than the standard method. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
distributed resource allocation, non-concave optimization, optimization, non-convex, resource allocation, computational optimization
in
Computational Optimization and Applications
volume
23
issue
2
pages
171 - 200
publisher
Kluwer
external identifiers
  • wos:000178468900002
  • scopus:0036853858
ISSN
0926-6003
DOI
10.1023/A:1020524817896
language
English
LU publication?
yes
id
f5f79200-9e9a-4f02-825b-75e269ca7321 (old id 326187)
date added to LUP
2007-08-07 08:24:41
date last changed
2017-01-01 07:14:31
@article{f5f79200-9e9a-4f02-825b-75e269ca7321,
  abstract     = {We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximisation version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with functions that are not necessarily concave is difficult. In this article, we focus on a large class of problem instances, with objective functions that are close to a concave function or some other smooth function, but with small irregularities in their shape. It is described that these properties are important in many practical situations. The irregularities make it hard or impossible to use known, efficient resource allocation techniques. We show that, for this class of functions the optimal solution can be computed efficiently. We support our claims by experimental evidence. Our experiments show that our algorithm in hard and practically relevant cases runs up to 40-60 times faster than the standard method.},
  author       = {Andersson, A and Carlsson, Per and Ygge, F},
  issn         = {0926-6003},
  keyword      = {distributed resource allocation,non-concave optimization,optimization,non-convex,resource allocation,computational optimization},
  language     = {eng},
  number       = {2},
  pages        = {171--200},
  publisher    = {Kluwer},
  series       = {Computational Optimization and Applications},
  title        = {Resource allocation with wobbly functions},
  url          = {http://dx.doi.org/10.1023/A:1020524817896},
  volume       = {23},
  year         = {2002},
}