A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model

Aleksandr Stolyar, Yuan Zhong

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

Abstract

We consider an infinite-server system, where multiple customers can be placed into one server for service simultaneously, subject to packing constraints. Customers are placed for service immediately upon arrival, and leave the system after service completion.

Original languageEnglish (US)
Title of host publication54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages319-326
Number of pages8
ISBN (Electronic)9781509045495
DOIs
StatePublished - Feb 10 2017
Externally publishedYes
Event54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 - Monticello, United States
Duration: Sep 27 2016Sep 30 2016

Publication series

Name54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

Other

Other54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
CountryUnited States
CityMonticello
Period9/27/169/30/16

Fingerprint

Randomized Algorithms
Greedy Algorithm
Packing
Optimality
Servers
Server
Customers
Immediately
Completion
Model

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Control and Optimization

Cite this

Stolyar, A., & Zhong, Y. (2017). A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model. In 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 (pp. 319-326). [7852247] (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2016.7852247

A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model. / Stolyar, Aleksandr; Zhong, Yuan.

54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016. Institute of Electrical and Electronics Engineers Inc., 2017. p. 319-326 7852247 (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016).

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

Stolyar, A & Zhong, Y 2017, A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model. in 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016., 7852247, 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Institute of Electrical and Electronics Engineers Inc., pp. 319-326, 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Monticello, United States, 9/27/16. https://doi.org/10.1109/ALLERTON.2016.7852247
Stolyar A, Zhong Y. A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model. In 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016. Institute of Electrical and Electronics Engineers Inc. 2017. p. 319-326. 7852247. (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016). https://doi.org/10.1109/ALLERTON.2016.7852247
Stolyar, Aleksandr ; Zhong, Yuan. / A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model. 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 319-326 (54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016).
@inproceedings{c2bef91f0c9947e9b54f578e6cd93a10,
title = "A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model",
abstract = "We consider an infinite-server system, where multiple customers can be placed into one server for service simultaneously, subject to packing constraints. Customers are placed for service immediately upon arrival, and leave the system after service completion.",
author = "Aleksandr Stolyar and Yuan Zhong",
year = "2017",
month = "2",
day = "10",
doi = "10.1109/ALLERTON.2016.7852247",
language = "English (US)",
series = "54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "319--326",
booktitle = "54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016",
address = "United States",

}

TY - GEN

T1 - A greedy randomized algorithm achieving sublinear optimality gap in a dynamic packing model

AU - Stolyar, Aleksandr

AU - Zhong, Yuan

PY - 2017/2/10

Y1 - 2017/2/10

N2 - We consider an infinite-server system, where multiple customers can be placed into one server for service simultaneously, subject to packing constraints. Customers are placed for service immediately upon arrival, and leave the system after service completion.

AB - We consider an infinite-server system, where multiple customers can be placed into one server for service simultaneously, subject to packing constraints. Customers are placed for service immediately upon arrival, and leave the system after service completion.

UR - http://www.scopus.com/inward/record.url?scp=85015189942&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015189942&partnerID=8YFLogxK

U2 - 10.1109/ALLERTON.2016.7852247

DO - 10.1109/ALLERTON.2016.7852247

M3 - Conference contribution

AN - SCOPUS:85015189942

T3 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

SP - 319

EP - 326

BT - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

PB - Institute of Electrical and Electronics Engineers Inc.

ER -