dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Deterministic randomness and unbalanced allocations

  • Start Date: July 23, 2013
  • Event Start Time: 12:30 PM
  • Event End Time: 1:30 PM
  • Organizers: Gene Fiorini
  • Seminar Series: REU Seminar
  • Presenter(s): Amanda Redlich - Rutgers University
  • Event Location: DIMACS Seminar room
  • Abstract: Often making a decision at random leads to a bad decision, but making a decision deterministically takes too long. Recently, there has been much research on algorithms that combine the best of both worlds. This talk builds on the balanced allocation algorithm first described by Azar, Broder, Karlin and Upfal. Their algorithm (and its relatives) uses the "power of two choices", combining randomness and determinism, to distribute balls into bins in a balanced way. Here, we are interested in distributing balls into bins in an unbalanced way. An algorithm for an unbalanced allocation is presented together with its analysis. This algorithm models some distributions arising in physics and queuing theory, and also decreases costs for many natural pricing functions.