Rui Wang |
王
睿
I’m a biology college student at Suzhou University of Science and Technology .My research interests are bioinformatics .
I'm also interested in more applied problems with nice theoretical components. Here is my CV(last updated Oct 2020) and research statement.
In my spare time, I maintain a WeChat Official Accounts Run blog “Biology Every Day”, breaking down newest research and biology findings into layman terms.
You can contact me through email wangrui.ts@qq.com.
See all publications.
Urban Complex Systems, .
Street parking spots for automobiles are a scarce commodity in most urban environments. The heterogeneity of car sizes makes it inefficient to rigidly define fixed-sized spots. Instead, unmarked streets in cities like New York leave placement decisions to individual drivers, who have no direct incentive to maximize street utilization. In this paper, we explore the effectiveness of two different behavioral interventions designed to encourage better parking, namely (1) educational campaigns to encourage parkers to "kiss the bumper" and reduce the distance between themselves and their neighbors, or (2) painting appropriately-spaced markings on the street and urging drivers to "hit the line". Through analysis and simulation, we establish that the greatest densities are achieved when lines are painted to create spots roughly twice the length of average-sized cars. Kiss-the-bumper campaigns are in principle more effective than hit-the-line for equal degrees of compliance, although we believe that the visual cues of painted lines induce better parking behavior.
SODA, .
We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph H=(V,E) with n=|V|, m=|E| and p=\sum_{e\in E}|e| the best known algorithm to compute a global minimum cut in H runs in time O(np) for the uncapacitated case and in O(np+n^2\log n) time for the capacitated case. We show the following new results.
- Given an uncapacitated hypergraph H and an integer k we describe an algorithm that runs in O(p) time to find a subhypergraph H' with sum of degrees O(kn) that preserves all edge-connectivities up to k (a k-sparsifier). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an O(p+\lambda n^2) time algorithm for computing a global minimum cut of H where \lambda is the minimum cut value.
- We generalize Matula's argument for graphs to hypergraphs and obtain a (2+\e)-approximation to the global minimum cut in a capacitated hypergraph in O(\frac{1}{\e}(p+n \log n)\log n) time.
- We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in O(np+n^2\log n) time and O(p) space. We utilize vertex ordering based ideas to obtain our results. Unlike graphs we observe that there are several different orderings for hypergraphs which yield different insights.
Frontiers in Genetics .
SIAM Journal on Discrete Mathematics .
Karger used spanning tree packings [D. R. Karger, J. ACM, 47 (2000), pp. 46--76] to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts. This is a different approach from his well-known random contraction algorithm [D. R. Karger, Random Sampling in Graph Optimization Problems, Ph.D. thesis, Stanford University, Stanford, CA, 1995, D. R. Karger and C. Stein, J. ACM, 43 (1996), pp. 601--640]. Thorup developed a fast deterministic algorithm for the minimum k-cut problem via greedy recursive tree packings [M. Thorup, Minimum k-way cuts via deterministic greedy tree packing, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 159--166]. In this paper we revisit properties of an LP relaxation for cͅut proposed by Naor and Rabani [Tree packing and approximating k-cuts, in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 103, SIAM, Philadelphia, 2001, pp. 26--27], and analyzed in [C. Chekuri, S. Guha, and J. Naor, SIAM J. Discrete Math., 20 (2006), pp. 261--271]. We show that the dual of the LP yields a tree packing that, when combined with an upper bound on the integrality gap for the LP, easily and transparently extends Karger's analysis for mincut to the k-cut problem. In addition to the simplicity of the algorithm and its analysis, this allows us to improve the running time of Thorup's algorithm by a factor of n. We also improve the bound on the number of \alpha-approximate k-cuts. Second, we give a simple proof that the integrality gap of the LP is 2(1-1/n). Third, we show that an optimum solution to the LP relaxation, for all values of k, is fully determined by the principal sequence of partitions of the input graph. This allows us to relate the LP relaxation to the Lagrangean relaxation approach of Barahona [Oper. Res. Lett., 26 (2000), pp. 99--105] and Ravi and Sinha [European J. Oper. Res., 186 (2008), pp. 77--90]; it also shows that the idealized recursive tree packing considered by Thorup gives an optimum dual solution to the LP.
SIAM Journal on Computing .
We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph H=(V,E) with n = |V|, m = |E| and p = \sum_{e \in E} |e| the fastest known algorithm to compute a global minimum cut in H runs in O(np) time for the uncapacitated case, and in O(np + n^2 \log n) time for the capacitated case. We show the following new results.
- Given an uncapacitated hypergraph H and an integer k we describe an algorithm that runs in O(p) time to find a (trimmed) subhypergraph H' with sum of degrees O(kn) that preserves all edge-connectivities up to k (a k-sparse certificate). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an O(p + \lambda n^2) time algorithm for computing a global minimum cut of H where \lambda is the minimum cut value.
- We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in O(np + n^2 \log n) time and O(p) space matching the asymptotic time to find a single minimum cut.
- We obtain a (2+\e)-approximation to the global minimum cut of a capacitated hypergraph in O(\frac{1}{\e} (p \log n + n \log^2 n)) time, and for uncapacitated hypergraphs in O(p/\e) time. We achieve this by generalizing Matula's algorithm for graphs to hypergraphs.
- We describe an algorithm to compute approximate strengths of all the edges of a hypergraph in O(p \log^2 n \log p) time. This gives a near linear time algorithm for finding a (1+\e)-cut sparsifier based on the work of Kogan and Krauthgamer. As a byproduct we obtain faster algorithms for various cut and flow problems in hypergraphs of small rank.
Our results build upon properties of vertex orderings that were inspired by the maximum adjacency ordering for graphs due to Nagamochi and Ibaraki. Unlike graphs we observe that there are several orderings for hypergraphs and these yield different insights.
2019, Submitted.
The capacitated vehicle routing problem (CVRP) is one of the most well known NP-hard combinatorial optimization problems. Single depot CVRP with a general metric is NP-hard even for fixed capacity 3, while polynomial time solvable for fixed capacity 2. We consider the variant of CVRP where restocking is available. We show that if there is a constant number of depots, then the problem can be solved in polynomial time when capacity is 2.
.
In this thesis, we consider cut and connectivity problems on graphs, digraphs, hypergraphs and hedgegraphs. The main results are the following:
- We introduce a faster algorithm for finding the reduced graph in element-connectivity computations. We also show its application to node separation.
- We present several results on hypergraph cuts, including (a) a near linear time algorithm for finding a (2 + ε)-approximate min-cut, (b) an algorithm to find a representation of all min-cuts in the same time as finding a single min-cut, (c) a sparse subgraph that preserves connectivity for hypergraphs and (d) a near linear-time hypergraph cut sparsifier.
- We design the first randomized polynomial time algorithm for the hypergraph k-cut problem whose complexity has been open for over 20 years. The algorithm generalizes to hedgegraphs with constant span.
- We address the complexity gap between global vs. fixed-terminal cuts problems in digraphs by presenting a 2-\frac{1}{448} approximation algorithm for the global bicut problem.