Blar i Department of Informatics på forfatter "Inamdar, Tanmay Nitin"
-
Algorithms for covering multiple submodular constraints and applications
Chekuri, Chandra; Inamdar, Tanmay Nitin; Quanrud, Kent; Varadarajan, Kasturi; Zhang, Zhao (Journal article; Peer reviewed, 2022)We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a weight function \(w: N \rightarrow \mathbb {R}_+\), r monotone submodular functions \(f_1,f_2,\ldots ,f_r\) over N and ... -
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Saurabh, Saket (Journal article; Peer reviewed, 2021)De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted ... -
Exact Exponential Algorithms for Clustering Problems
Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Purohit, Nidhi; Saurabh, Saket (Journal article; Peer reviewed, 2022)In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely k-MEDIAN and k-MEANS. In k-MEDIAN, the input consists of a set X of n points belonging to a metric ... -
Non-Uniform k-Center and Greedy Clustering
Inamdar, Tanmay Nitin; Varadarajan, Kasturi (Journal article; Peer reviewed, 2022)In the Non-Uniform k-Center (NUkC) problem, a generalization of the famous k-center clustering problem, we want to cover the given set of points in a metric space by finding a placement of balls with specified radii. In ... -
(Re)packing Equal Disks into Rectangle
Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Zehavi, Meirav (Journal article; Peer reviewed, 2022)The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following ...