46 citations · 114 across the 18 of their papers we have counts for
20 papers
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 $…
Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
Konstantin Makarychev, Ilias Papanikolaou, Liren Shan
We study the problem of explainable k-medians clustering introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020). In this problem, the goal is to construct a threshold dec…
LiD-FL: Towards List-Decodable Federated Learning
Hong Liu, Liren Shan, Han Bao +3
Federated learning is often used in environments with many unverified participants. Therefore, federated learning under adversarial attacks receives significant attention. This pap…
Error-Tolerant E-Discovery Protocols
Jinshuo Dong, Jason D. Hartline, Liren Shan +1
We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) in the context of electronic discovery (e-discovery). Based on a request…
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…
Optimal Scoring Rules for Multi-dimensional Effort
Jason D. Hartline, Liren Shan, Yingkai Li +1
This paper develops a framework for the design of scoring rules to optimally incentivize an agent to exert a multi-dimensional effort. This framework is a generalization to strateg…
Algorithmic Learning Foundations for Common Law
Jason D. Hartline, Daniel W. Linna, Liren Shan +1
This paper looks at a common law legal system as a learning algorithm, models specific features of legal proceedings, and asks whether this system learns efficiently. A particular…
Explainable k-means. Don't be greedy, plant bigger trees!
Konstantin Makarychev, Liren Shan
We provide a new bi-criteria competitive algorithm for explainable -means clustering. Explainable -means was recently introduced by Dasgupta, Frost, Mos…
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…
Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models
Yuhao Yi, Liren Shan, Philip E. Paré +1
This paper studies algorithmic strategies to effectively reduce the number of infections in susceptible-infected-recovered (SIR) epidemic models. We consider a Markov chain SIR mod…
Improved Guarantees for k-means++ and k-means++ Parallel
Konstantin Makarychev, Aravind Reddy, Liren Shan
In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved ap…
Optimization of Scoring Rules
Jason D. Hartline, Yingkai Li, Liren Shan +1
We characterize the optimal reward functions (scoring rules) that incentivize an agent to acquire information and report it truthfully to the principal. The optimal scoring rules l…
Stochastic Linear Optimization with Adversarial Corruption
Yingkai Li, Edmund Y. Lou, Liren Shan
We extend the model of stochastic bandits with adversarial corruption (Lykouriset al., 2018) to the stochastic linear optimization problem (Dani et al., 2008). Our algorithm is agn…
Improving information centrality of a node in complex networks by adding edges
Liren Shan, Yuhao Yi, Zhongzhi Zhang
The problem of increasing the centrality of a network node arises in many practical applications. In this paper, we study the optimization problem of maximizing the information cen…
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…
Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
Liren Shan, Huan Li, Zhongzhi Zhang
The minimum dominating set (MDS) problem is a fundamental subject of theoretical computer science, and has found vast applications in different areas, including sensor networks, pr…