Research
Publications
- Balanced Friendly Partitions of Random Digraphs
Lily Li, Aleksandar Nikolov
In submission.Abstract
The friendly bisection problem for a digraph $G = (V,E)$ seeks to partition the vertices of $G$ into two equal sized parts so that every vertex has $\gamma$ more neighbors in its own part than the opposing one. This problem and its variants --- usually stated for undirected graphs --- have been studied in a few different communities including graph theory, social choice, discrete optimization, and statistical physics. We consider the directed case and the directed case when partitioning into $k$ equally sized parts, which generalizes two equal parts. Our primary tool is the second moment method which we use to show that, for random digraphs, friendly bisections exist for $\gamma \ge -1$ with positive probability, and, for $k > 2$, under a numerical assumption, balanced friendly $k$-partitions exist for $\gamma = \Omega(\sqrt{|V|})$ with high probability.
- On the Gap Between Hereditary Discrepancy and the Determinant Lower Bound
Lily Li, Aleksandar Nikolov
SIAM Journal on Discrete Mathematics, 2024. (article)Abstract
The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151--160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of $m$ subsets of a universe of size $n$ is on the order of $\max\left\{ \log n, \sqrt{\log m}\right\}$. On the other hand, building upon work of Matoušek [Proc. Amer. Math. Soc., 141 (2013), pp. 451--460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308--313] showed that this gap is always bounded up to constants by $\sqrt{\log(m) \log(n)}$. This is tight when $m$ is polynomial in $n$ but leaves open the case of large $m$. We show that the bound of Jiang and Reis is tight for nearly the entire range of $m$. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products.
- Partitioning friends fairly
Lily Li, Evi Micha, Aleksandar Nikolov, Nisarg Shah
AAAI 2023. (article)Abstract
We consider the problem of partitioning $n$ agents in an undi- rected social network into $k$ almost equal in size (differing by at most one) groups, where the utility of an agent for a group is the number of her neighbors in the group. The core and envy-freeness are two compelling axiomatic fairness guarantees in such settings. The former demands that there be no coalition of agents such that each agent in the coalition has more utility for that coalition than for her own group, while the latter demands that no agent envy another agent for the group they are in. We provide (often tight) approximations to both fairness guarantees, and many of our positive results are obtained via efficient algorithms.
- On the Computational Complexity of Linear Discrepancy
Lily Li, Aleksandar Nikolov
ESA 2020. (article)Abstract
Many problems in computer science and applied mathematics require rounding a vector $w$ of fractional values lying in the interval $[0,1]$ to a binary vector x so that, for a given matrix $A$, $Ax$ is as close to $Aw$ as possible. For example, this problem arises in LP rounding algorithms used to approximate NP-hard optimization problems and in the design of uniformly distributed point sets for numerical integration. For a given matrix $A$, the worst-case error over all choices of $w$ incurred by the best possible rounding is measured by the linear discrepancy of $A$, a quantity studied in discrepancy theory, and introduced by Lovasz, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151--160]. We initiate the study of the computational complexity of linear discrepancy. Our investigation proceeds in two directions: (1) proving hardness results and (2) finding both exact and approximate algorithms to evaluate the linear discrepancy of certain matrices. For (1), we show that linear discrepancy is NP-hard. Thus we do not expect to find an efficient exact algorithm for the general case. Restricting our attention to matrices with a constant number of rows, we present a poly-time exact algorithm for matrices consisting of a single row and matrices with a constant number of rows and entries of bounded magnitude. We also present an exponential-time approximation algorithm for general matrices, and an algorithm that approximates linear discrepancy to within an exponential factor.
- Open-loop collective assembly using a light field to power and control a phototaxic mini-robot swarm
Adam Bignell, Lily Li, Richard Vaughan
ICRA 2019. (article)Abstract
We propose a novel scheme that jointly addresses the problems of powering and coordinating a population of mini-robots for collective construction. In our setting, a population of simple mobile robots must push blocks into desired polygonal shapes. Each robot performs only simple phototaxis. Coordination is purely open-loop: a global light field guides and powers the robots. We demonstrate this concept in simulation and explore a series of dynamic light field design strategies that robustly result in assembled shapes including nonconvex polygons.
- Minimum Enclosing Circle Problem with Base Point
Binay Bhattacharya, Lily Li
CCCG 2017. (article)Abstract
This article presents a linear time algorithm to solve a variant of the minimum enclosing circle (MEC) problem. The inputs are a point set $S$ of size $n$, and a point $b$ in the plane called the free point. Our goal is to locate a circle center $o^∗$ such that the maximum distance of all points in $S$ to $o^∗$ divided by the distance from $o^∗$ to $b$ is minimized. The original investigation by Qiu et al. (preprint) found an $O(n \log n)$ algorithm using the furthest point Voronoi diagram of the point set $S$. This problem can be formulated as a generalized linear programming problem when the domain for the optimal solution is restricted and therefore, can be solved in linear expected time [Algorithmica, 16 (1992), pp. 498--516]. We describe here a simple deterministic linear time algorithm based on Meggido’s prune-and-search solution to the standard problem [SIAM Journal on Computing 12, 4 (1983), pp. 759--776]. We extend our technique to solve similar variants of the MEC problem where the free point is replaced with other geometric objects such as a free line, a free line segment, and a set of free points.
Thesis
Discrepancy and Related Problems (article)
PhD Thesis, University of Toronto.