Conference paper · 2011

Near optimal online algorithms and fast approximation algorithms for resource allocation problems

Nikhil R. Devanur, Kamal Kishore Jain, Balasubramanian Sivan, Christopher A. Wilkens

ACM Conference on Electronic Commerce (EC), 29–38 · Published 5 June 2011 · DOI 10.1145/1993574.1993581

View at the publisherCite this paper

In brief

“Near optimal online algorithms and fast approximation algorithms for resource allocation problems” is a 2011 conference paper by Nikhil R. Devanur and 3 co-authors, published in ACM Conference on Electronic Commerce (EC). OpenAlex counts 204 citations as of 19 November 2026, which puts it in the top 2% of works published in 2011 by citations. The publisher's version is not open access, and OpenAlex records no free legal copy.

Citations
204
Most cited in
2021 (18)
Field-weighted impact
8.97
References
26
Authors
4

Abstract

We present algorithms for a class of resource allocation problems both in the online setting with stochastic input and in the offline setting. This class of problems contains many interesting special cases such as the Adwords problem. In the online setting we introduce a new distributional model called the adversarial stochastic input model, which is… Read the full abstract at the publisher.

Excerpt. This paper is not open access.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Devanur, N. R., Jain, K. K., Sivan, B., & Wilkens, C. A. (2011). Near optimal online algorithms and fast approximation algorithms for resource allocation problems. ACM Conference on Electronic Commerce (EC), 29–38. https://doi.org/10.1145/1993574.1993581

MLA 9

Devanur, Nikhil R., et al. “Near optimal online algorithms and fast approximation algorithms for resource allocation problems.” ACM Conference on Electronic Commerce (EC), 2011, pp. 29–38. https://doi.org/10.1145/1993574.1993581.

Chicago

Devanur, Nikhil R., Kamal Kishore Jain, Balasubramanian Sivan, and Christopher A. Wilkens. 2011. “Near optimal online algorithms and fast approximation algorithms for resource allocation problems.” ACM Conference on Electronic Commerce (EC): 29–38. https://doi.org/10.1145/1993574.1993581.

Harvard

Devanur, N. R. et al. (2011) ‘Near optimal online algorithms and fast approximation algorithms for resource allocation problems’, ACM Conference on Electronic Commerce (EC), pp. 29–38. doi:10.1145/1993574.1993581.

IEEE

N. R. Devanur, K. K. Jain, B. Sivan, and C. A. Wilkens, “Near optimal online algorithms and fast approximation algorithms for resource allocation problems,” ACM Conference on Electronic Commerce (EC), pp. 29–38, 2011, doi: 10.1145/1993574.1993581.

BibTeX

@inproceedings{devanur2011near,
  title     = {{Near optimal online algorithms and fast approximation algorithms for resource allocation problems}},
  author    = {Devanur, Nikhil R. and Jain, Kamal Kishore and Sivan, Balasubramanian and Wilkens, Christopher A.},
  booktitle = {ACM Conference on Electronic Commerce (EC)},
  year      = {2011},
  pages     = {29--38},
  doi       = {10.1145/1993574.1993581},
  url       = {https://doi.org/10.1145/1993574.1993581}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
20171717
20181616
20191717
20201616
20211818
20221818
20231111
202477
202577
202655

Its field-weighted citation impact is 8.97: it has been cited 8.97 times as often as the average work of the same field, type and year (1.00 is the world average).

Topic and keywords

Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems

  • resource allocation
  • online algorithms
  • approximation algorithms
  • competitive ratio
  • randomized algorithms

Work with this paper

Most-cited papers in Mathematics

All highly cited Mathematics papers

Questions about this paper

How do I cite this paper in APA style?

Devanur, N. R., Jain, K. K., Sivan, B., & Wilkens, C. A. (2011). Near optimal online algorithms and fast approximation algorithms for resource allocation problems. ACM Conference on Electronic Commerce (EC), 29–38. https://doi.org/10.1145/1993574.1993581

How many times has this paper been cited?

204 times, according to OpenAlex on 19 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

OpenAlex records no free legal copy. Check your library's access, the authors' pages or a repository, or ask the corresponding author for a copy.

Who wrote this paper?

Nikhil R. Devanur, Kamal Kishore Jain, Balasubramanian Sivan, Christopher A. Wilkens.

What is the DOI of this paper?

10.1145/1993574.1993581, permanently at https://doi.org/10.1145/1993574.1993581. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 19 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.