15 citations · 22 across the 14 of their papers we have counts for
16 papers
Sum-of-Max Partition under a Knapsack Constraint
Kai Jin, Danna Zhang, Canhui Zhang
Sequence partition problems arise in many fields, such as sequential data analysis, information transmission, and parallel computing. In this paper, we study the following partitio…
String Rearrangement Inequalities and a Total Order Between Primitive Words
Ruixi Luo, Taikun Zhu, Kai Jin
We study the following rearrangement problem: Given words, rearrange and concatenate them so that the obtained string is lexicographically smallest (or largest, respectively).…
A Generalization of Self-Improving Algorithms
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin +1
Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances follow some unknown \emph{product…
A note on self-improving sorting with hidden partitions
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin
We study self-improving sorting with hidden partitions. Our result is an optimal algorithm which runs in expected time O(H(π(I)) + n), where I is the given input which contains n e…
On the Complexity of Computing the Topology of Real Algebraic Space Curves
Kai Jin, Jin-San Cheng
In this paper, we present a deterministic algorithm to find a strong generic position for an algebraic space curve. We modify our existing algorithm for computing the topology of a…
Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon
Kai Jin, Zhiyi Huang
We study the problem of computing the minimum area triangle that circumscribes a given -sided convex polygon touching edge-to-edge. In other words, we compute the minimum area t…
Finding all Maximal Area Parallelograms in a Convex Polygon
Kai Jin
Polygon inclusion problems have been studied extensively in geometric optimization. In this paper, we consider the variant of computing the maximum area parallelograms (MAPs) and a…
A technique for solving the polygon inclusion problems
Kai Jin, Taikun Zhu, Ruixi Luo
We propose a technique called Rotate-and-Kill for solving the polygon inclusion and circumscribing problems. By applying this technique, we obtain time algorithms for comput…
On 1-factorizations of Bipartite Kneser Graphs
Kai Jin
It is a challenging open problem to construct an explicit 1-factorization of the bipartite Kneser graph , which contains as vertices all -element and -element sub…
On the Turaev genus of torus knots
Kaitian Jin, Adam M. Lowrance, Eli Polston +1
The Turaev genus and dealternating number of a link are two invariants that measure how far away a link is from alternating. We determine the Turaev genus of a torus knot with five…
Linear Time Approximation Schemes for Geometric Maximum Coverage
Kai Jin, Jian Li, Haitao Wang +2
We study approximation algorithms for the following geometric version of the maximum coverage problem: Let be a set of weighted points in the plane. Let repre…
On the power of dominated players in team competitions
Kai Jin, Pingzhong Tang, Shiteng Chen
We investigate multi-round team competitions between two teams, where each team selects one of its players simultaneously in each round and each player can play at most once. The c…
A Geometric Structure Associated with the Convex Polygon
Kai Jin
We propose a geometric structure induced by any given convex polygon , called , which is an arrangement of line segments, each of which is parallel to an edge…
Linear Time Approximation Schemes for Geometric Maximum Coverage
Jian Li, Haitao Wang, Bowei Zhang +1
We study approximation algorithms for the following geometric version of the maximum coverage problem: Let P be a set of n weighted points in the plane. We want to place m a * b re…
A Generic Position Based Method for Real Root Isolation of Zero-Dimensional Polynomial Systems
Jin-San Cheng, Kai Jin
We improve the local generic position method for isolating the real roots of a zero-dimensional bivariate polynomial system with two polynomials and extend the method to general ze…
Certified Rational Parametric Approximation of Real Algebraic Space Curves with Local Generic Position Method
Jin-San Cheng, Kai Jin, Xiao-Shan Gao +1
In this paper, an algorithm to compute a certified rational parametric approximation for algebraic space curves is given by extending the local generic position method for so…