SIAM Undergraduate Research Online
Volume 13
In This Volume

Competitive Algorithms for Bulk Allocation under Uncertainty: The Caterer's Problem
Published electronically November 19, 2020DOI: 10.1137/20S1355549
Authors
Arjun Kodialam (Marlboro High School)
Project Advisors
T.V. Lakshman (Nokia Bell Labs)
Abstract
We consider the problem of allocating resources to meet an uncertain demand. There are well studied approaches to solve this problem when distributional information is known about the demand. We consider this resource allocation problem when we lack information about the statistics of the demand. These types of resource allocation problems, where there is only minimal information available about the demand, arises naturally in many instances. The motivation for studying this problem is the allocation of resources (testing kits, masks) for pandemic control. While resources are being allocated, there is only minimal information known about the demand size. Decision makers have to solve some version of the Caterer’s problem when making advance reservation of resources (processing, storage) in the cloud for new applications. We develop deterministic and randomized competitive algorithms for the Caterer’s problem. Unlike the closely related online Skirental problem, the Caterer’s problem does not satisfy the principle of equality and this makes the Caterer’s problem more challenging. We prove the optimality of the randomized algorithms by using Yao’s Lemma and developing matching lower bounds for the problem.

Best Strategy for Each Team in The Regular Season to Win Champion in The Knockout Tournament
Published electronically November 14, 2020 
Online Learning and Matching for Resource Allocation Problems
Published electronically October 13, 2020 
Keep on Trucking
Published electronically August 25, 2020 
Using Mathematics to Assess the Impact of Insecticidebased Interventions and Vaccination on Malaria Control
Published electronically August 11, 2020 
Including Batter Sprint Speed in the Calculation of the Intrinsic Value of a Batted Ball
Published electronically August 11, 2020 
Stochastic Automata Networks and Tensors with Application to Chemical Kinetics
Published electronically July 28, 2020 
A Mathematical Model of Biofilm Growth on Degradable Substratum
Published electronically June 17, 2020 
Bounds on Rate of Convergence for the Shuffled Discrete Heat Equation in Zd
Published electronically April 29, 2020 
Distributions of Matching Distances in Topological Data Analysis
Published electronically April 14, 2020 
The FitzhughNagumo System as a Model of Human Cardiac Action Potentials
Published electronically March 11, 2020 
Periodic Properties of Expansions for Fractions into any Base
Published electronically January 24, 2020 
Geodesic Active Contours with Shape Priors for Segmentation, Disocclusion, and Illusory Contour Capture
Published electronically January 24, 2020
Become a SIURO Author
Publish your undergraduate research with SIAM to experience all aspects of the peer review process — from submission, review and revision, to publication.
Submit a Paper to SIUROStay UptoDate with Email Alerts
Sign up for our monthly newsletter and emails about other topics of your choosing.