Talk by Dr. Arindam Khan, Assistant Professor, Dept. of CSA

Location: CSA Seminar Hall (Room No. 254, First Floor)

Department of Computer Science and Automation
CSA Faculty Colloquium

Speaker : Dr. Arindam Khan
Assistant Professor
Dept. of CSA

Title : Optimization under uncertainty: online algorithms for knapsack and generalized assignment problem.

Date : Friday, April 26, 2019

Time : 4:00 PM

Venue : CSA Seminar Hall (Room No. 254, First Floor)

Abstract

For online optimization, the input instance is revealed in a sequence of steps and, after each step, the algorithm has to take an immediate and irrevocable decision based on the previous inputs. Online algorithms produce a sequence of decisions for such problems without the complete information of the future. In the worst-case analysis of online optimization problems, sometimes, it is impossible to achieve any bounded competitive ratio. An interesting way to bypass these impossibility results is to incorporate a stochastic component into the input model. In random-order arrival model, the adversary specifies an input instance in advance but the input appears according to a random permutation. In this talk we will present improved competitive algorithms under random-order arrival, for two classical optimization problems: knapsack and generalized assignment problem (GAP).

The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. For random-order arrival, we develop a (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 [Kesselheim et al. STOC ’14]. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, our approach yields a (1/6.99)-competitive algorithm for GAP.

This is joint work with Susanne Albers and Leon Ladewig.

Biography of the speaker

Arindam Khan is an Assistant Professor at the Department of Computer Science and Automation (CSA) at Indian Institute of Science, Bangalore. He obtained his PhD in Algorithms, Combinatorics, and Optimization (ACO) from School of Computer Science at Georgia Institute of Technology, Atlanta, USA. Before that he got his B. Tech and M. Tech (Dual Degree) from the Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, India. He did his postdoc from IDSIA, Switzerland and TU Munich, Germany. He is broadly interested in the design and analysis of algorithms and theoretical computer science. His current research focus is on Approximation Algorithms, Online Algorithms, and Combinatorial Optimization. He is also interested in Computational Geometry, Graph Algorithms, and Parameterized Algorithms.

Host Faculty : Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar

ALL ARE WELCOME