Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

A φ-competitive algorithm for scheduling packets with deadlines

Tools
- Tools
+ Tools

Veselý, Pavel, Chrobak, Marek, Łukasz, Jeż and Sgall, Jiří (2019) A φ-competitive algorithm for scheduling packets with deadlines. In: ACM-SIAM Symposium on Discrete Algorithms (SODA19), San Diego, California, USA, 6-9 Jan 2019. Published in: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA19) ISBN 9781611975482. doi:10.1137/1.9781611975482.9

[img]
Preview
PDF
WRAP-φ-competitive-algorithm-scheduling-packets-deadlines-Vesely-2019.pdf - Published Version - Requires a PDF viewer.

Download (1251Kb) | Preview
[img] PDF
WRAP-φ-competitive-algorithm-scheduling-packets-deadlines-Vesely-2018.pdf - Accepted Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (708Kb)
[img] PDF
dcs-191118-wrap--soda19-copyright (002).pdf - Other
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (88Kb)
Official URL: https://doi.org/10.1137/1.9781611975482.9

Request Changes to record.

Abstract

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a ϕ-competitive online algorithm for PacketScheduling (where ϕ ≈ 1.618 is the golden ratio), matching the previously established lower bound.

Item Type: Conference Item (Paper)
Divisions: Faculty of Science > Computer Science
Journal or Publication Title: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA19)
Publisher: SIAM
ISBN: 9781611975482
Official Date: 2019
Dates:
DateEvent
2019Published
6 January 2019Available
27 September 2018Accepted
DOI: 10.1137/1.9781611975482.9
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Conference Paper Type: Paper
Title of Event: ACM-SIAM Symposium on Discrete Algorithms (SODA19)
Type of Event: Conference
Location of Event: San Diego, California, USA
Date(s) of Event: 6-9 Jan 2019
Related URLs:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us