39 citations · 308 across the 129 of their papers we have counts for
7 papers · 1 filter
On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
We study the parameterized complexity of approximating the -Dominating Set (DomSet) problem where an integer and a graph on vertices are given as input, and the goal…
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz +4
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable…
Asymptotic Existence of Fair Divisions for Groups
Pasin Manurangsi, Warut Suksompong
The problem of dividing resources fairly occurs in many practical situations and is therefore an important topic of study in economics. In this paper, we investigate envy-free divi…
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi
The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph and a set of demand pairs. The aim is to com…
Inapproximability of VC Dimension and Littlestone's Dimension
Pasin Manurangsi, Aviad Rubinstein
We study the complexity of computing the VC Dimension and Littlestone's Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x…
Inapproximability of Maximum Biclique Problems, Minimum -Cut and Densest At-Least--Subgraph from the Small Set Expansion Hypothesis
Pasin Manurangsi
The Small Set Expansion Hypothesis (SSEH) is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose edge expansio…
Computing an Approximately Optimal Agreeable Set of Items
Pasin Manurangsi, Warut Suksompong
We study the problem of finding a small subset of items that is \emph{agreeable} to all agents, meaning that all agents value the subset at least as much as its complement. Previou…