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 Ski-rental 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 Insecticide-based 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 Fitzhugh-Nagumo 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 Up-to-Date with Email Alerts
Sign up for our monthly newsletter and emails about other topics of your choosing.