eCommons

 

REAL TIME OPTIMIZATION IN NETWORKS: PRACTICAL ALGORITHMS WITH PROVABLE GUARANTEES

dc.contributor.authorVera, Alberto
dc.contributor.chairBanerjee, Siddhartha
dc.contributor.committeeMemberKleinberg, Robert
dc.contributor.committeeMemberSamaranayake, Samitha
dc.contributor.committeeMemberShmoys, David
dc.date.accessioned2020-08-10T20:23:57Z
dc.date.available2020-08-10T20:23:57Z
dc.date.issued2020-05
dc.description300 pages
dc.description.abstractWe 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.
dc.identifier.doihttps://doi.org/10.7298/c1yc-9n65
dc.identifier.otherVera_cornellgrad_0058F_11977
dc.identifier.otherhttp://dissertations.umi.com/cornellgrad:11977
dc.identifier.urihttps://hdl.handle.net/1813/70387
dc.language.isoen
dc.rightsAttribution 4.0 International
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.titleREAL TIME OPTIMIZATION IN NETWORKS: PRACTICAL ALGORITHMS WITH PROVABLE GUARANTEES
dc.typedissertation or thesis
dcterms.licensehttps://hdl.handle.net/1813/59810
thesis.degree.disciplineOperations Research and Information Engineering
thesis.degree.grantorCornell University
thesis.degree.levelDoctor of Philosophy
thesis.degree.namePh. D., Operations Research and Information Engineering

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Vera_cornellgrad_0058F_11977.pdf
Size:
2.74 MB
Format:
Adobe Portable Document Format