Back to search

Cornell University

Approximation and online algorithms for the digital information world: supporting fairness and allowing recourse

Abstract

dc:description.abstract

The efforts to design better algorithms and heuristics for several important optimization problems has led to the invention of a rich variety of sophisticated algorithmic ideas. However, these techniques often rely on knowing the exact realization of client requests in advance (the offline setting), an unrealistic assumption. Although much work has been done on the online versions of these problems (in which the requests appear one at a time and decisions must be made without knowing the future), there is a significant gap between the theoretical guarantees obtainable in the online setting and when the entire input is known. In this dissertation, we will seek to bridge this gap using the notion of recourse: Recourse operations essentially enable us to modify decisions that turned out to be sub-optimal. For example, we will, within the context of scheduling, show that for the load balancing problem on unrelated machines, we can almost completely bridge the gap with an average of logarithmically many re-assignments. Unfortunately, several of the algorithmic solutions for both offline and online problems can often lead to unfair outcomes. For example, requests from certain demographic groups may be declined at much higher rates than average. The first part of this thesis develops new algorithmic techniques to obtain fair outcomes with near-optimal cost for a key problem in inventory management: the Joint Replenishment Problem (JRP). A part of this thesis will study a recent generalization of the online JRP which incorporates a notion of holding and delay costs and show that the primal-dual frameworks developed by prior work can be lifted to handle this important consideration with minimal loss in competitiveness.

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
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Suriyanarayana, Varun
Chair dc:contributor.chair
  • Shmoys, David
Committee members dc:contributor.committeemember
  • Williamson, David
  • Banerjee, Siddhartha

Subjects

dc:subject × 6

Rights

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

Identifiers

dc:identifier.*
Dc Identifier Bibid
17422564
Dc Identifier Other
ProQuest Submission ID: 15239
ProQuest Publication ID: 32171121

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

Suriyanarayana, Varun. Approximation and online algorithms for the digital information world: supporting fairness and allowing recourse. Doctor of Philosophy thesis, Cornell University, 2025. https://hdl.handle.net/1813/120757