Ke Shi |
史
可
I am a Master's student at USTC, currently under the guidance of Shuai Shao.
Prior to this, I earned my Bachelor's degree in Computer Science from UESTC while conducting theoretical computer science research under the guidance of Chao Xu.
My research interests revolve around algorithms and combinatorial optimization. Recently, my focus has been directed towards approximate counting algorithms and their correlations with the phenomenon of phase transitions in statistical physics.
You can contact me through email self.ke.shi@gmail.com or ke.shi@ustc.edu.
See all publications.
SODA .
In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f:2^V\to \R, computing a k-partition \{ V_1, \ldots, V_k \} of V with minimum \sum_{i=1}^k f(V_i). The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for k \leq 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem.
COCOON .
A subset B of ring \Z_n is called a \ell-covering set if \{ ab \pmod n \mid 0\leq a \leq \ell, b\in B\} = \Z_n. We show there exists a \ell-covering set of \Z_n of size O(\frac{n}{\ell}\log n) for all n and \ell, and how to construct such set. We also show examples where any \ell-covering set must have size \Omega(\frac{n}{\ell}\frac{\log n}{\log \log n}). The proof uses a refined bound for relative totient function obtained through sieve theory, and existence of a large divisor with linear divisor sum.
Mathematical Programming .
In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f:2^V\to \R, computing a k-partition \{ V_1, \ldots, V_k \} of V with minimum \sum_{i=1}^k f(V_i). The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for k \leq 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem.
Some manuscripts are available upon request.
2024, Submitted.
We study the connections between strong spatial mixing and zero-freeness, the two main notions used to devise deterministic approximation algorithms for counting problems. Following a recent framework introduced by [Regts, G. (2023). Absence of zeros implies strong spatial mixing. Probability Theory and Related Fields, 186(1), 621-641.] for the vertex model, we show that the implication from zero-freeness of the partition function to strong spatial mixing also works for the matching polynomial, a typical counting problem in the edge model. Based on Heilmann and Lieb's results, a zero-free region C_\Delta=\C \backslash (-\infty,-\frac{1}{4(\Delta-1)}] of the partition function and a Christoffel--Darboux type identity, we give a very simple proof for strong spatial mixing of the matching polynomial on graphs of degree bounded by \Delta with any complex edge parameter z \in C_\Delta. This proof does not rely on the tree recursion which is commonly used for proving strong spatial mixing in previous results.
2024, Submitted.
We prove a totally novel form of strong spatial mixing (SSM) for the ferromagnetic Ising model in terms of edge activities. This SSM property holds for the entire zero-free region of Lee--Yang Theorem, i.e., \beta>1 and |\lambda|<1 or symmetrically |\lambda|>1. We also prove a form of SSM in terms of external fields in a smaller region \beta>1 and |\lambda|<1/\beta or symmetrically |\lambda|>\beta. These SSM properties can be exploited to devise FPTASes via Weitz's and Barvinok's algorithms. Our proof is based on the framework introduced by [Regts, G. (2023). Absence of zeros implies strong spatial mixing. Probability Theory and Related Fields, 186(1), 621-641.], namely local dependence of coefficients (LDC) and a uniform bound implies SSM. In order to establish LDC, we prove a division relation for the 2-spin system on general graphs.
2024, Submitted.
The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem. In SCP, pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on tree structures. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle. We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices.