Guohui Lin

collaborators

4 papers

cs.GT2025

Maximizing social welfare among EF1 allocations at the presence of two types of agents

Jiaxuan Ma, Yong Chen, Guangting Chen +3

We study the fair allocation of indivisible items to $n$ agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are o…

cs.DS2025

An improved local search based algorithm for $k^{-}$ -star partition

Mingyang Gong, Guohui Lin, Brendan Mumey

We study the $k^{-}$ -star partition problem that aims to find a minimum collection of vertex-disjoint stars, each having at most $k$ vertices to cover all vertices in a simple undire…

cs.DS2024

Approximation algorithms for non-sequential star packing problems

Mengyuan Hu, An Zhang, Yong Chen +2

For a positive integer $k \geq 1$ , a $k$ -star ( $k^{+}$ -star, $k^{-}$ -star, respectively) is a connected graph containing a degree- $ℓ$ vertex and $ℓ$ degree- $1$ vertices, where $\e…

cs.DS2024

Approximately covering vertices by order- $5$ or longer paths

Mingyang Gong, Zhi-Zhong Chen, Guohui Lin +1

This paper studies $M P C_{v}^{5 +}$ , which is to cover as many vertices as possible in a given graph $G = (V, E)$ by vertex-disjoint $5^{+}$ -paths (i.e., paths each with at least five verti…

Maximizing social welfare among EF1 allocations at the presence of two types of agents

An improved local search based algorithm for k−-star partition

Approximation algorithms for non-sequential star packing problems

Approximately covering vertices by order-5 or longer paths

An improved local search based algorithm for $k^{-}$ -star partition

Approximately covering vertices by order- $5$ or longer paths