Publications

You can also find my articles on my Google Scholar profile.

Journal Articles

Simple linear time algorithm for sorting strings in omega-order with applications

Published in Acta Informatica, 2026

We present a simple linear time algorithm for the following sorting problem: Given $n$ words $A_1,\ldots,A_n$, find a permutation $\{\pi_1,\ldots,\pi_n\}$ of $1,\ldots,n$ so that $(A_{\pi_1})^\omega\leq\ldots\leq(A_{\pi_n})^\omega$, where $(A)^\omega$ denotes the infinitely repeating string $AAA\ldots$. Let $L$ denote the total length of the given strings. We note that the running time of our algorithm is $O(L)$ even if the size of alphabet is beyond $O(1)$. We also present an $O(L+n \log n)$ time algorithm for the restricted model where we are only allowed to compare symbols. In other words, the main result of this paper is that the time complexity of sorting (in lexicographic order) is the same as that of sorting (in $\omega$ order) under all common models (bounded alphabet, unbounded alphabet, compare-based model). Our main results find applications in related problems such as rearranging and concatenating given words so that the result is lexicographically smallest or largest.

Recommended citation: Luo, R., Zhu, T. & Jin, K. Simple linear time algorithm for sorting strings in omega-order with applications. Acta Informatica 63, 17 (2026). https://doi.org/10.1007/s00236-026-00530-5
Download Paper | Download Bibtex

Optimal Allocations Under Strongly Pigou–Dalton Criteria: Hidden Layer Structure and Efficient Combinatorial Approach

Published in Mathematics, 2026

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 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, the Gini Index, Entropy, and Envy Sum. We also design efficient algorithms for finding a stable allocation, including an $O(m^{2}n)$ time algorithm for the case of indivisible items, and an $O(m^{2}n^{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 zero for the case of divisible items under binary additive valuations, and is at most one for the case of indivisible items under binary submodular valuations.

Recommended citation: Zhu, T., Jin, K., Luo, R., & Cao, S. (2026). Optimal Allocations Under Strongly Pigou–Dalton Criteria: Hidden Layer Structure and Efficient Combinatorial Approach. Mathematics, 14(4), 658.
Download Paper | Download Bibtex

Simple $k$-Crashing Plan with a Good Approximation Ratio

Published in Mathematics, 2025

In project management, a project is typically described as an activity-on-edge network, where each activity / job is represented as an edge of some network $N$ (which is a directed acyclic graph). To speed up the project (i.e., reduce the duration), the manager can crash a few jobs (namely, reduce the length of the corresponding edges) by investing extra resources into those jobs. Greedily and repeatedly choosing the cheapest solution to crash the project by one unit is the simplest way to achieve the crashing goal and has been implemented countless times throughout the history. However, the algorithm does not guarantee an optimum solution and analysis of it is limited. Through theoretical analysis, we prove that the above algorithm has an approximation ratio upper bound of $\frac{1}{1}+\ldots+\frac{1}{k}$ for this $k$-crashing problem.

Recommended citation: Luo, R., Jin, K., & Ye, Z. (2025). Simple k-Crashing Plan with a Good Approximation Ratio. Mathematics, 13(14), 2234.
Download Paper | Download Bibtex

Conference Papers

Sum-of-Max Chain Partition of a Tree

Published in International Computing and Combinatorics Conference (COCOON 2025), 2025

Path partition problems on trees have found various applications. In this paper, we present an $O(n \log n)$ time algorithm for solving the following variant of path partition problem: sum-of-max chain partition of a tree. The problem is NP-complete for arbitrary graphs. Furthermore, we extended the algorithm to the sum-of-dominant case, in which the cost of a chain is determined by the highest-ranked vertex’s cost.

Recommended citation: Luo, R., Zhu, T., Jin, K. (2026). Sum-of-Max Chain Partition of a Tree. In: Fomin, F.V., Xiao, M. (eds) Computing and Combinatorics. COCOON 2025. Lecture Notes in Computer Science, vol 15984. Springer, Singapore. https://doi.org/10.1007/978-981-95-0218-9_5
Download Paper | Download Bibtex

Simple $k$-Crashing Plan with a Good Approximation Ratio

Published in 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), 2024

A project is considered as an activity-on-edge network (AOE network, which is a directed acyclic graph) $N$, where each activity / job of the project is an edge. Some jobs must be finished before others can be started, as described by the topology structure of $N$. It is known that job $j_i$ in normal speed would take $b_i$ days to be finished after it is started, and hence the (normal) duration of the project $N$, denoted by $d(N)$, is determined, which equals the length of the critical path (namely, the longest path) of $N$. To speed up the project, the manager can crash a few jobs (namely, reduce the length of the corresponding edges) by investing extra resources into that job. However, the time for completing $j_i$ has a lower bound due to technological limits - it requires at least $a_i$ days to be completed. Following the convention, assume that the duration of a job has a linear relation with the extra resources put into this job; equivalently, there is a parameter $c_i$ (slope), so that shortening $j_i$ by $d~(0\leq d \leq b_i-a_i)$ days costs $c_i\cdot d$ resources. Given project $N$ and an integer $k \geq 1$, the \emph{$k$-crashing problem} asks the minimum cost to speed up the project by $k$ days. In this paper, we present a simple solution with the approximation ratio $\frac{1}{1}+\ldots+\frac{1}{k}$. For simplicity, we focus on the linear case throughout the paper, but our proofs are still correct for the convex case, where shortening an edge becomes more difficult after a previous shortening.

Recommended citation: Luo, R., Jin, K., & Ye, Z. (2024, May). Simple k-crashing Plan with a Good Approximation Ratio. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (pp. 2366-2368).
Download Paper | Download Bibtex

Luo, Ruixi (罗睿熙)