Back to search

University of Washington

Vector Balancing and Integer Programming

Abstract

dc:description.abstract

A set of 2n pennies can be easily balanced into two groups of equal weight, yet doing so by tossing each coin would incur a standard deviation of O(sqrt(n)) as an imbalance in the weight of the two groups. More realistically, when running randomized controlled trials for vaccines and deciding who will receive a vaccine and who will receive a placebo, it is desirable to design robust experiments which are also balanced. This is because significant imbalances, say in the average age of each group or in any other relevant attribute, reduce the value of the experiment. Balancing has found other applications in fair resource allocation, differential privacy, bin packing, and scheduling. We start by motivating the study of vector balancing with five fascinating open problems (Chapter 0). We show improved vector balancing bounds for several classes of convex bodies, such as Lp balls, zonotopes and Schatten balls (Chapters 2, 3 and 7). We explore connections to sparsification of convex combinations (Chapter 4) and graphs (Chapter 6). We investigate the tightness of approximations to a robust notion of balancing (Chapter 5), prefix balancing problems (Chapter 8) and online settings (Chapter 9). Finally, we give a faster algorithm for integer programming (Chapter 10), a fundamental problem in discrete optimization, by providing a constructive answer to a question of Kannan and Lovasz and Dadush on the subspace flatness of convex bodies.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Oliveira Reis, Victor
Advisor dc:contributor.advisor
  • Rothvoss, Thomas

Subjects

dc:subject × 8

Rights

dc:rights
Statement dc:rights
  • none
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/51136

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Oliveira Reis, Victor. Vector Balancing and Integer Programming. 2024. http://hdl.handle.net/1773/51136