4 citations · 16 across the 17 of their papers we have counts for
36 papers
Envy-free Allocations with Individual Payments
Robert Bredereck, Eva Deltl, Tanmay Inamdar +2
When an envy-free allocation of indivisible goods does not exist, monetary transfers can restore envy-freeness. Existing work on fair division with subsidies, however, typically as…
Reaching Fairness by Reallocating Goods
Robert Bredereck, Eva Deltl, Tanmay Inamdar +3
Fair allocation of indivisible goods has largely been studied under the assumption that no prior allocation exists. Motivated by practical settings with pre-existing (and possibly…
Minimum Envy Graphical House Allocation Beyond Identical Valuations
Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
House allocation is an extremely well-studied problem in the field of fair allocation, where the goal is to assign houses to agents while satisfying certain fairness criter…
Clustering under Constraints: Efficient Parameterized Approximation Schemes
Sujoy Bhore, Ameet Gadekar, Tanmay Inamdar
We present a unified framework that yields EPASes for constrained -clustering in metric spaces of bounded (algorithmic) scatter dimension, a notion introduced by Abbasi et a…
Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
Ameet Gadekar, Tanmay Inamdar
Hybrid -Clustering is a model of clustering that generalizes two of the most widely studied clustering objectives: -Center and -Median. In this model, given a set of p…
Parameterized Geometric Graph Modification with Disk Scaling
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph and an integer $k\in\mathb…
Hybrid k-Clustering: Blending k-Median and k-Center
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clusetring problem, given a set P of…
Cuts in Graphs with Matroid Constraints
Aritra Banik, Fedor V. Fomin, Petr A. Golovach +3
{\sc Vertex -Cut} and {\sc Vertex Multiway Cut} are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these probl…
When far is better: The Chamberlin-Courant approach to obnoxious committee selection
Sushmita Gupta, Tanmay Inamdar, Pallavi Jain +3
Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance a…
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov +3
In MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula , and , and the goal is to find an assignment with at most variables set t…
Controlling Delegations in Liquid Democracy
Shiri Alouf-Heffetz, Tanmay Inamdar, Pallavi Jain +2
In liquid democracy, agents can either vote directly or delegate their vote to a different agent of their choice. This results in a power structure in which certain agents possess…
FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu +2
For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as paramete…
Diamond on ladder systems and countably metacompact topological spaces
Rodrigo Carvalho, Tanmay Inamdar, Assaf Rinot
The property of countable metacompactness of a topological space gets its importance from Dowker's 1951 theorem that the product of a normal space X with the unit interval is again…
Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem
Walter Didimo, Fedor V. Fomin, Petr A. Golovach +3
A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all…
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +1
We study the \textsc{-Fixed Cardinality Graph Partitioning (-FCGP)} problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In…
Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability
Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh +1
In the Minimum Bisection problem, input is a graph and the goal is to partition the vertex set into two parts and , such that and the number of edg…
Kernelization for Spreading Points
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance,…
Fixed-Parameter Algorithms for Fair Hitting Set Problems
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu +2
Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of…
FPT Approximations for Capacitated/Fair Clustering with Outliers
Rajni Dabas, Neelima Gupta, Tanmay Inamdar
Clustering problems such as -Median, and -Means, are motivated from applications such as location planning, unsupervised learning among others. In such applications, it is im…
Coresets for Clustering in Geometric Intersection Graphs
Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar
Designing coresets--small-space sketches of the data preserving cost of the solutions within -approximate factor--is an important research direction in the study of cente…
Proportionally Fair Matching with Multiple Groups
Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar +1
The study of fair algorithms has become mainstream in machine learning and artificial intelligence due to its increasing demand in dealing with biases and discrimination. Along thi…
Clustering What Matters: Optimal Approximation for Clustering with Outliers
Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh +1
Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set of points and two integers and , the clustering with outliers aims…
(Re)packing Equal Disks into Rectangle
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
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 ov…
On strong chains of sets and functions
Tanmay Inamdar
Shelah has shown that there are no chains of length increasing modulo finite in . We improve this result to sets. That is, we show that there are no chains of le…