Online set packing and competitive scheduling of multi-part tasks

Almenn færsla
dc.contributor.authorEmek, Yuval
dc.contributor.authorHalldórsson, Magnús M.
dc.contributor.authorMansour, Yishay
dc.contributor.authorPatt-Shamir, Boaz
dc.contributor.authorRadhakrishnan, Jaikumar
dc.contributor.authorRawitz, Dror
dc.contributor.departmentDepartment of Computer Science
dc.date.accessioned2026-10-08T13:57:01Z
dc.date.available2026-10-08T13:57:01Z
dc.date.issued2010-07-25
dc.description.abstractWe consider a scenario where large data frames are broken into a few packets and transmitted over the network. Our focus is on a bottleneck router: the model assumes that in each time step, a set of packets (a burst) arrives, from which only one packet can be served, and all other packets are lost. A data frame is considered useful only if none of its constituent packets is lost, and otherwise it is worthless. We abstract the problem as a new type of online set packing, present a randomized distributed algorithm and a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximal burst size and the maximal number of packets per frame. We also present refined bounds that depend on the uniformity of these parameters.en
dc.description.versionPeer revieweden
dc.format.extent10
dc.format.extent431384
dc.format.extent440-449
dc.format.extent
dc.identifier.citationEmek, Y, Halldórsson, M M, Mansour, Y, Patt-Shamir, B, Radhakrishnan, J & Rawitz, D 2010, Online set packing and competitive scheduling of multi-part tasks. in PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery (ACM), pp. 440-449, 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, 25/07/10. https://doi.org/10.1145/1835698.1835800en
dc.identifier.citationconferenceen
dc.identifier.doi10.1145/1835698.1835800
dc.identifier.isbn9781605588889
dc.identifier.other251164292
dc.identifier.othera81cd91d-0e20-4e64-9137-c89bbb308e17
dc.identifier.other77956250701
dc.identifier.urihttps://hdl.handle.net/20.500.11815/8589
dc.language.isoen
dc.publisherAssociation for Computing Machinery (ACM)
dc.relation.ispartofseriesPODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing; ()en
dc.relation.ispartofseriesProceedings of the Annual ACM Symposium on Principles of Distributed Computing; ()en
dc.relation.urlhttps://www.scopus.com/pages/publications/77956250701en
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.subjectCompetitive analysisen
dc.subjectMulti-packet framesen
dc.subjectOnline set packingen
dc.subjectPacket fragmentationen
dc.subjectSoftwareen
dc.subjectHardware and Architectureen
dc.subjectComputer Networks and Communicationsen
dc.titleOnline set packing and competitive scheduling of multi-part tasksen
dc.type/dk/atira/pure/researchoutput/researchoutputtypes/contributiontobookanthology/conferenceen

Skrár

Original bundle

Niðurstöður 1 - 1 af 1
Nafn:
1835698.1835800.pdf
Stærð:
421.27 KB
Snið:
Adobe Portable Document Format
Hlaða niður

Undirflokkur

Háskólinn í Reykjavík

Öll gögn í Opnum vísindum eru vernduð af ákvæðum höfundalaga og með öllum réttindum áskildum, nema annað sé tekið fram.