BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Kai Jin

Kai Jin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational GeometryComputer Science and Game Theoryastro-ph.IMComputational ComplexityData Structures and Algorithmseess.SYMultiagent Systemsphysics.app-phphysics.ins-detSymbolic ComputationSystems and Control

Catalog footprint

What is connected

10works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2026arXiv

Optimal Allocations under Strongly Pigou-Dalton Criteria: Hidden Layer Structure & Efficient Combinatorial Approach

We investigate optimal social welfare allocations of $m$ items to $n$ agents with binary additive or submodular valuations. For binary additive valuations, we prove that the set of optimal allocations coincides with the set of so-called \emph{stable allocations}, as long as the employed criterion for evaluating social welfare is strongly Pigou-Dalton (SPD) and symmetric. Many common criteria are SPD and symmetric, such as Nash social welfare, leximax, leximin, Gini index, entropy, and envy sum. We also design efficient algorithms for finding a stable allocation, including an $O(m^2n)$ time algorithm for the case of indivisible items, and an $O(m^2n^5)$ time one for the case of divisible items. The first is faster than the existing algorithms or has a simpler analysis. The latter is the first combinatorial algorithm for that problem. It utilizes a hidden layer partition of items and agents admitted by all stable allocations, and cleverly reduces the case of divisible items to the case of indivisible items.In addition, we show that the profiles of different optimal allocations have a small Chebyshev distance, which is 0 for the case of divisible items under binary additive valuations, and is at most 1 for the case of indivisible items under binary submodular valuations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon

We study the problem of computing the minimum area triangle that circumscribes a given $n$-sided convex polygon touching edge-to-edge. In other words, we compute the minimum area triangle that is the intersection of 3 half-planes out of $n$ half-planes defined by a given convex polygon. Building on the Rotate-and-Kill technique {Arxiv:1707.04071}, we propose an algorithm that solves the problem in $O(n)$ time, improving the best-known $O(n\log n)$ time algorithms given in [A. Aggarwal et. al. DCG94; B. Schieber. SODA95}. Our algorithm computes all the locally minimal area circumscribing triangles touching edge-to-edge.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

String Rearrangement Inequalities and a Total Order Between Primitive Words

We study the following rearrangement problem: Given $n$ words, rearrange and concatenate them so that the obtained string is lexicographically smallest (or largest, respectively). We show that this problem reduces to sorting the given words so that their repeating strings are non-decreasing (or non-increasing, respectively), where the repeating string of a word $A$ refers to the infinite string $AAA\ldots$. Moreover, for fixed size alphabet $Σ$, we design an $O(L)$ time sorting algorithm of the words (in the mentioned orders), where $L$ denotes the total length of the input words. Hence we obtain an $O(L)$ time algorithm for the rearrangement problem. Finally, we point out that comparing primitive words via comparing their repeating strings leads to a total order, which can further be extended to a total order on the finite words (or all words).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A floating top-electrode electrowetting-on-dielectric system

Herein, we describe a novel device configuration for double-plate electrowetting-on-dielectric system with a floating top-electrode. As conventional double-plate EWOD device requires a grounded electrode on top-plate, it will cause additional fabrication complicity and cost during the encapsulation process. In this work, we found that by carefully designing electrode arrangement and configuring driving electronic circuit, the droplet driving force can be maintained with a floating electrode on the top-plate. This can provide the possibilities to integrate additional electrical or electrochemical sensing functions on the top-plate. We use both finite element analysis and fabricated system to validate the theory, and the results indicate that floating top-electrode EWOD systems are highly reliable and reproducible once the design considerations are fully met.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Generalization of Self-Improving Algorithms

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots,x_n$ follow some unknown \emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $\mathsf{D}_i$, and the $x_i$'s are drawn independently. After spending $O(n^{1+\varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/\varepsilon)$, where $H \in \{H_\mathrm{S},H_\mathrm{DT}\}$, and $H_\mathrm{S}$ and $H_\mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$'s under the \emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$'s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$'s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$'s are well-behaved. After an $O(\mathrm{poly}(n))$-time training phase, we achieve $O(n + H_\mathrm{S})$ and $O(nα(n) + H_\mathrm{DT})$ expected running times for sorting and DT, respectively, where $α(\cdot)$ is the inverse Ackermann function.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Impedance Sensing Platform for Monitoring Heterogeneous Connectivity and Diagnostics in Lab-on-a-Chip Systems

Reliable hardware connectivity is vital in heterogeneous integrated systems. For example, in digital microfluidics lab-on-a-chip systems, there are hundreds of physical connections required between a micro-electro-mechanical fabricated device and the driving system that can be remotely located on a printed-circuit-board. Unfortunately, the connection reliability cannot be checked or monitored by vision-based detection methods that are commonly used in the semiconductor industry. Therefore, a sensing platform that can be seamlessly integrated into existing digital microfluidics systems and provide real-time monitoring of multi-connectivity is highly desired. Here, we report an impedance sensing platform that can provide fast detection of a single physical connection in timescales of milli-seconds. Once connectivity is established, the same set-up can be used to determine droplet location. The sensing system can be scaled up to support multiple channels or applied to other heterogeneously integrated systems that require real-time monitoring and diagnostics of multi-connectivity systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Sodium laser guide star coupling efficiency measurement method

Large telescope's adaptive optics (AO) system requires one or several bright artificial laser guide stars to improve its sky coverage. The recent advent of high power sodium laser is perfect for such application. However, besides the output power, other parameters of the laser also have significant impact on the brightness of the generated sodium laser guide star mostly in non-linear relationships. When tuning and optimizing these parameters it is necessary to tune based on a laser guide star generation performance metric. Although return photon flux is widely used, variability of atmosphere and sodium layer make it difficult to compare from site to site even within short time period for the same site. A new metric, coupling efficiency is adopted in our field tests. In this paper, we will introduce our method for measuring the coupling efficiency of a 20W class pulse sodium laser for AO application during field tests that were conducted during 2013-2015.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the power of dominated players in team competitions

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 competition defines an extensive-form game with perfect recall and can be solved efficiently by standard methods. We are interested in the properties of the subgame perfect equilibria of this game. We first show that uniformly random strategy is a subgame perfect equilibrium strategy for both teams when there are no redundant players (i.e., the number of players in each team equals to the number of rounds of the competition). Secondly, a team can safely abandon its weak players if it has redundant players and the strength of players is transitive. We then focus on the more interesting case where there are redundant players and the strength of players is not transitive. In this case, we obtain several counterintuitive results. First of all, a player might help improve the payoff of its team, even if it is dominated by the entire other team. We give a necessary condition for a dominated player to be useful. We also study the extent to which the dominated players can increase the payoff. These results bring insights into playing and designing general team competitions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Generic Position Based Method for Real Root Isolation of Zero-Dimensional Polynomial Systems

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 zero-dimensional polynomial systems. The method mainly involves resultant computation and real root isolation of univariate polynomial equations. The roots of the system have a linear univariate representation. The complexity of the method is $\tilde{O}_B(N^{10})$ for the bivariate case, where $N=\max(d,τ)$, $d$ resp., $τ$ is an upper bound on the degree, resp., the maximal coefficient bitsize of the input polynomials. The algorithm is certified with probability 1 in the multivariate case. The implementation shows that the method is efficient, especially for bivariate polynomial systems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Certified Rational Parametric Approximation of Real Algebraic Space Curves with Local Generic Position Method

In this paper, an algorithm to compute a certified $G^1$ rational parametric approximation for algebraic space curves is given by extending the local generic position method for solving zero dimensional polynomial equation systems to the case of dimension one. By certified, we mean the approximation curve and the original curve have the same topology and their Hausdauff distance is smaller than a given precision. Thus, the method also gives a new algorithm to compute the topology for space algebraic curves. The main advantage of the algorithm, inhering from the local generic method, is that topology computation and approximation for a space curve is directly reduced to the same tasks for two plane curves. In particular, the error bound of the approximation space curve is obtained from the error bounds of the approximation plane curves explicitly. Nontrivial examples are used to show the effectivity of the method.

0 citations0 reviewsNo code linkedOpen access