3 Search Results for "Keshav, Srinivasan"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.10
Improved Approximation Guarantees for Advertisement Placement

Authors: Waldo Gálvez, Roberto Oliva, and Victor Verdugo

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
The advertisement placement problem involves selecting and scheduling ads within a timeline that has capacity constraints to maximize profit. Each task is characterized by its height, width, and profit, and must be fully scheduled across multiple time slots. This problem models practical scenarios such as internet advertising and energy management, and it also generalizes classical combinatorial optimization problems like the knapsack and bin packing problems. We present a simple (2+ε)-approximation algorithm for any ε > 0, which improves upon the state-of-the-art 3+ε factor established by Freund and Naor twenty years ago. Our approach combines rounding techniques with dynamic programming and an efficient extension of list scheduling. Furthermore, we enhance this method with linear programming techniques to provide an almost optimal (1+ε)-approximation algorithm under resource augmentation, which allows for a slight increase in time slot capacities.
Cite as

Waldo Gálvez, Roberto Oliva, and Victor Verdugo. Improved Approximation Guarantees for Advertisement Placement. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2025.10,
  author =	{G\'{a}lvez, Waldo and Oliva, Roberto and Verdugo, Victor},
  title =	{{Improved Approximation Guarantees for Advertisement Placement}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  URN =		{urn:nbn:de:0030-drops-243762},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  annote =	{Keywords: Advertisement Placement, Two-dimensional Packing, Geometric Knapsack, Resource Allocation}
}
Document
DOI: 10.4230/DagRep.11.6.14
Towards Climate-Friendly Internet Research (Dagstuhl Seminar 21272)

Authors: Vaibhav Bajpai, Oliver Hohlfeld, Jon Crowcroft, and Srinivasan Keshav

Published in: Dagstuhl Reports, Volume 11, Issue 6 (2021)

Abstract
This report presents guidelines for deciding when virtual or hybrid conferences are suitable and how to design them. The report is the output from a Dagstuhl seminar where the goal was to review the current status of virtual conferences and to develop best practices for hybrid conferences. The participants provided input on the state-of-the-art of virtual conferences: what works, what does not, and what needs improvement. From this discussion, the participants discussed the requirements, implications, and guidelines for designing hybrid conferences. The participants felt that in the future, small research meetings will move entirely online whereas larger ones will be held as hybrid events.
Cite as

Vaibhav Bajpai, Oliver Hohlfeld, Jon Crowcroft, and Srinivasan Keshav. Towards Climate-Friendly Internet Research (Dagstuhl Seminar 21272). In Dagstuhl Reports, Volume 11, Issue 6, pp. 14-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{bajpai_et_al:DagRep.11.6.14,
  author =	{Bajpai, Vaibhav and Hohlfeld, Oliver and Crowcroft, Jon and Keshav, Srinivasan},
  title =	{{Towards Climate-Friendly Internet Research (Dagstuhl Seminar 21272)}},
  pages =	{14--37},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{6},
  editor =	{Bajpai, Vaibhav and Hohlfeld, Oliver and Crowcroft, Jon and Keshav, Srinivasan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.6.14},
  URN =		{urn:nbn:de:0030-drops-155780},
  doi =		{10.4230/DagRep.11.6.14},
  annote =	{Keywords: Carbon Footprint, Energy Efficient Networking, Climate Change}
}
Document
DOI: 10.4230/DagSemProc.05142.3
An Architecture for Tetherless Communication

Authors: Aaditeshwar Seth, Patrick Darragh, Suihong Liang, Yunfeng Lin, and Srinivasan Keshav

Published in: Dagstuhl Seminar Proceedings, Volume 5142, Disruption Tolerant Networking (2005)

Abstract
In the emerging paradigm of tetherless computing, client applications running on small, inexpensive, and smart mobile devices maintain opportunistic wireless connectivity with back-end services running on centralized computers, enabling novel classes of applications. These applications require a communications infrastrastructure that is mobility-aware, disconnection-resilient and provides support for an opportunistic style of communiction. It should even be able to function across network partitions that may arise when end-to-end communication is not possible. We outline, design, and evaluate the implementation of an architecture that provides this functionality. we shot that it is possible for next-generation mobile devices to obtain up to 80-fold improvement over conventional mechanisms by exploiting opportunistic WiFi links, and that this benefit can be delivered as an overlay that is compatible with the current Internet.
Cite as

Aaditeshwar Seth, Patrick Darragh, Suihong Liang, Yunfeng Lin, and Srinivasan Keshav. An Architecture for Tetherless Communication. In Disruption Tolerant Networking. Dagstuhl Seminar Proceedings, Volume 5142, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{seth_et_al:DagSemProc.05142.3,
  author =	{Seth, Aaditeshwar and Darragh, Patrick and Liang, Suihong and Lin, Yunfeng and Keshav, Srinivasan},
  title =	{{An Architecture for Tetherless Communication}},
  booktitle =	{Disruption Tolerant Networking},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5142},
  editor =	{Marcus Brunner and Lars Eggert and Kevin Fall and J\"{o}rg Ott and Lars Wolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05142.3},
  URN =		{urn:nbn:de:0030-drops-3519},
  doi =		{10.4230/DagSemProc.05142.3},
  annote =	{Keywords: Delay tolerant networks, Opportunistic communication, Tetherless computing, Wireless, Mobile}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021
  • 1 2005

  • Refine by Author
  • 2 Keshav, Srinivasan
  • 1 Bajpai, Vaibhav
  • 1 Crowcroft, Jon
  • 1 Darragh, Patrick
  • 1 Gálvez, Waldo
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 1 Networks
  • 1 Social and professional topics
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Advertisement Placement
  • 1 Carbon Footprint
  • 1 Climate Change
  • 1 Delay tolerant networks
  • 1 Energy Efficient Networking
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact