MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Online Integer Packing

Naveen Garg
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS  
AG Audience
English

Date, Time and Location

Tuesday, 5 December 2006
13:30
30 Minutes
E1 4
024
Saarbrücken

Abstract

An integer packing problem is an integer program of the form: max c^Tx subject to Ax <= b, x is integer and the entries of A,b,c are non-negative. In the online version of this problem, the columns of A arrive online. When the j^{th} column arrives we set the variable x_j and this cannot be modified subsequently.


This model captures online virtual circuit routing, load balancing etc. In this talk I will present the first algorithm for this problem.

Contact

Naveen Garg
115
--email hidden
passcode not visible
logged in users only

Naveen Garg, 12/04/2006 11:20 AM
Naveen Garg, 11/20/2006 01:59 PM
Naveen Garg, 11/08/2006 12:07 PM -- Created document.