Geometry in Optimization: To Choose or Not to Choose
Abstract:
Geometry lies at the heart of optimization, where the seemingly simple decision of "to choose or not to choose an object" often uncovers profound insights into the structure and solutions of complex problems. This geometric perspective has wide-ranging applications across various fields, including machine learning, logistics, computer graphics, sensor networks, and many others. In this talk, I will focus on two fundamental aspects of geometric optimization problems: Packing and Independence.
Consider a set of D-dimensional objects (each with associated profits), and the goal is to find the maximum profit subset that can be packed non-overlappingly into a given D-dimensional hypercube. This problem is known as the Geometric Knapsack Problem. The packing of various kinds of objects has been extensively studied in Mathematics over the centuries. Interestingly, the problem becomes computationally intractable, even in rather simple settings, e.g., unit disks in 2D. In this talk, I will present a polynomial time approximation scheme for packing D-dimensional balls.
On the other hand, the Independent Set problem for a set of objects in D-dimensional space aims to find a maximum-cardinality subset of independent (i.e., pairwise-disjoint) objects. Independent set is one of the most fundamental problems in Theoretical Computer Science, and unfortunately, it is known to be inapproximable in the most general cases. There has been extensive research on polynomial-time algorithms with improved approximation ratios for geometric inputs, sometimes trading off efficiency in running times. In this talk, I will present near-linear time constant-factor approximation algorithms for various natural families of objects, e.g., rectangles, balls, etc.
Bio:
Sujoy is a faculty member in the Department of Computer Science & Engineering at the Indian Institute of Technology Bombay and a visiting fellow in the Department of Mathematics at the London School of Economics. Previously, he was a postdoctoral research fellow at the Faculty of Informatics, TU Vienna, and the Department of Computer Science, ULB Brussels. He received his Ph.D. from the Department of Computer Science, Faculty of Natural Sciences, Ben-Gurion University. Sujoy has been the recipient of the Krietman doctoral fellowship, BSF fellowship, London Mathematical Society fellowship, and Young Faculty Award at IIT Bombay.