46 citations · 114 across the 18 of their papers we have counts for
8 papers · 1 filter
Socially Fair Clustering: Parameterized Approximation and Local Search
Aditya Anand, Yury Makarychev, Liren Shan
We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $…
Higher-Order Cheeger Inequality for Partitioning with Buffers
Konstantin Makarychev, Yury Makarychev, Liren Shan +1
We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph . The buffered expansion of a set with…
Approximation Algorithms for Norm Multiway Cut
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev +2
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph into parts so as to separate given terminals. Recently, Chandrasekaran…
Random Cuts are Optimal for Explainable k-Medians
Konstantin Makarychev, Liren Shan
We show that the RandomCoordinateCut algorithm gives the optimal competitive ratio for explainable k-medians in l1. The problem of explainable k-medians was introduced by Dasgupta,…
Dynamic Curing and Network Design in SIS Epidemic Processes
Yuhao Yi, Liren Shan, Shijie Wang +2
This paper studies efficient algorithms for dynamic curing policies and the corresponding network design problems to guarantee the fast extinction of epidemic spread in a susceptib…
Near-optimal Algorithms for Explainable k-Medians and k-Means
Konstantin Makarychev, Liren Shan
We consider the problem of explainable -medians and -means introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian~(ICML 2020). In this problem, our goal is to find a thres…
Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
Liren Shan, Huan Li, Zhongzhi Zhang
As a fundamental subject of theoretical computer science, the maximum independent set (MIS) problem not only is of purely theoretical interest, but also has found wide applications…
Current Flow Group Closeness Centrality for Complex Networks
Huan Li, Richard Peng, Liren Shan +2
Current flow closeness centrality (CFCC) has a better discriminating ability than the ordinary closeness centrality based on shortest paths. In this paper, we extend this notion to…