Cost-oblivious reallocation for scheduling and planning

Michael A. Bender, Martín Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    In a reallocating-scheduler problem, jobs may be inserted and deleted from the system over time. Unlike in traditional online scheduling problems, where a job's placement is immutable, in reallocation problems the schedule may be adjusted, but at some cost. The goal is to maintain an approximately optimal schedule while also minimizing the reallocation cost for changing the schedule. This paper gives a reallocating scheduler for the problem of assigning jobs to p (identical) servers so as to minimize the sum of completion times to within a constant factor of optimal, with an amortized reallocation cost for a lengthw job of O(f(w) · log log Δ), where Δ is the length of the longest job and f() is the reallocation-cost function. Our algorithm is cost oblivious, meaning that the algorithm is not parameterized by f(), yet it achieves this bound for any subadditive f(). Whenever f() is strongly subadditive, the reallocation cost becomes O(f(w)). To realize a reallocating scheduler with low reallocation cost, we design a k-cursor sparse table. This data structure stores a dynamic set of elements in an array, with insertions and deletions restricted to k "cursors" in the structure. The data structure achieves an amortized cost of O(log k) for insertions and deletions, while also guaranteeing that any prefix of the array has constant density. Observe that this bound does not depend on n, the number of elements, and hence this data structure, restricted to k < n cursors, beats the lower bound of Ω(log n) for general sparse tables.

    Original languageEnglish (US)
    Title of host publicationSPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures
    PublisherAssociation for Computing Machinery
    Number of pages12
    ISBN (Electronic)9781450335881
    StatePublished - Jun 13 2015
    Event27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 - Portland, United States
    Duration: Jun 13 2015Jun 15 2015

    Publication series

    NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures


    Conference27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015
    Country/TerritoryUnited States


    • Cost-oblivious problems
    • Reallocation
    • Resource allocation

    ASJC Scopus subject areas

    • Software
    • Theoretical Computer Science
    • Hardware and Architecture


    Dive into the research topics of 'Cost-oblivious reallocation for scheduling and planning'. Together they form a unique fingerprint.

    Cite this