Back to search

Cornell University

REAL TIME OPTIMIZATION IN NETWORKS: PRACTICAL ALGORITHMS WITH PROVABLE GUARANTEES

Abstract

dc:description.abstract

We consider several optimization problems where the main challenge is to answer to a stream of requests. We provide algorithms that are efficient, practical, enjoy performance guarantees, and work well in practice. The first problem we study is computing Constrained Shortest Paths at scale. Even though the underlying optimization problem is NP-Hard, we can give parametric guarantees for the space requirement and running time of our algorithm. We use precomputation techniques, generalize the notion of Highway Dimension, and prove that, under mild conditions, we can scale Constrained Shortest Path whenever we can scale Shortest Path. We study also a large family of Resource Allocation and Pricing problems. We give a unified treatment and provide an algorithm that achieves constant regret, i.e., constant additive loss, in several problems. As special cases we can cover, we mention Online Packing (Network Revenue Management), Online Matching, Online Probing, and Pricing of Multiple Items. Our results hold even under several generalizations, such as restocking of resources and queues of customers with abandonment. Additionally, we present several robustness results in cases where the parameters of the problem are misspecified, similar to Bandits problems, or when there are two conflicting objectives, namely reward maximization and cost minimization. Furthermore, we also study the case when the arrival distribution can be accessed only via historical data and show that a single trace is enough to maintain constant regret guarantees.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Vera, Alberto
Chair dc:contributor.chair
  • Banerjee, Siddhartha
Committee members dc:contributor.committeemember
  • Kleinberg, Robert
  • Samaranayake, Samitha
  • Shmoys, David

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
13254532
Dc Identifier Other
ProQuest Submission ID: 11977
ProQuest Publication ID: 27963108

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Vera, Alberto. REAL TIME OPTIMIZATION IN NETWORKS: PRACTICAL ALGORITHMS WITH PROVABLE GUARANTEES. Doctor of Philosophy thesis, Cornell University, 2020. https://hdl.handle.net/1813/70387