6 papers
Approximately Partitioning Vertices into Short Paths
Mingyang Gong, Zhi-Zhong Chen, Brendan Mumey
Given a fixed positive integer and a simple undirected graph , the {\em -path partition} problem, denoted by PP for short, aims to find a minimum collection…
Computing Maximal Repeating Subsequences in a String
Mingyang Gong, Adiesha Liyanage, Braeden Sopp +1
In this paper we initiate the study of computing a maximal (not necessarily maximum) repeating pattern in a single input string, where the corresponding problems have been studied…
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 agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are o…
An improved local search based algorithm for -star partition
Mingyang Gong, Guohui Lin, Brendan Mumey
We study the -star partition problem that aims to find a minimum collection of vertex-disjoint stars, each having at most vertices to cover all vertices in a simple undire…
Approximation algorithms for scheduling with rejection in green manufacturing
Mingyang Gong, Brendan Mumey
Motivated by green manufacturing, this paper investigates a scheduling with rejection problem subject to an energy consumption constraint. Machines are associated with non-uniform…
Approximation algorithms for non-sequential star packing problems
Mengyuan Hu, An Zhang, Yong Chen +2
For a positive integer , a -star (-star, -star, respectively) is a connected graph containing a degree- vertex and degree- vertices, where $\e…