Resource allocation with wobbly functions

A Andersson, Per Carlsson, F Ygge

    Research output: Contribution to journalArticlepeer-review

    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.
    Original languageEnglish
    Pages (from-to)171-200
    JournalComputational Optimization and Applications
    Volume23
    Issue number2
    DOIs
    Publication statusPublished - 2002

    Subject classification (UKÄ)

    • Computer Science

    Free keywords

    • distributed resource allocation
    • non-concave optimization
    • optimization
    • non-convex
    • resource allocation
    • computational optimization

    Fingerprint

    Dive into the research topics of 'Resource allocation with wobbly functions'. Together they form a unique fingerprint.

    Cite this