Source author record

Mingyang Gong

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Formal Languages and Automata Theory

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Approximation algorithms for scheduling with rejection in green manufacturing

Motivated by green manufacturing, this paper investigates a scheduling with rejection problem subject to an energy consumption constraint. Machines are associated with non-uniform energy consumption rates, defined as the energy consumed per unit time. Each job is either rejected with a rejection penalty or accepted and scheduled on some machine for processing, which incurs energy consumption. The problem aims to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs while the total energy consumption is bounded by a given threshold. In this paper, when the number of machines is part of the input, we develop the first $(2+ε)$ -approximation algorithm for any fixed constant $ε$ and a simple QPTAS as well as a PTAS for uniform energy consumption rates. Moreover, we present an FPTAS when the number of machines is a fixed constant.

preprint2026arXiv

Computing Maximal Repeating Subsequences in a String

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 (e.g., a maximal common subsequence) only in two or more input strings by Hirota and Sakai starting 2019. Given an input string $S$ of length $n$ , we can compute a maximal square subsequence of $S$ in $O(n\log n)$ time, greatly improving the $O(n^2)$ bound for computing the longest square subsequence of $S$ . For a maximal $k$ -repeating subsequence, our bound is $O(f(k)n\log n)$ , where $f(k)$ is a computable function such that $f(k) < k\cdot 4^k$ . This greatly improves the $O(n^{2k-1})$ bound for computing a longest $k$ -repeating subsequence of $S$ , for $k\geq 3$ . Both results hold for the constrained case, i.e., when the solution must contain a subsequence $X$ of $S$ , though with higher running times.

preprint2022arXiv

Approximation algorithms for covering vertices by long paths

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least $k$ vertices is considered long. When $k \le 3$ , the problem is polynomial time solvable; when $k$ is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed $k \ge 4$ , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a $k$ -approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when $k = 4$ , the problem admits a $4$ -approximation algorithm which was presented recently. We propose the first $(0.4394 k + O(1))$ -approximation algorithm for the general problem and an improved $2$ -approximation algorithm when $k = 4$ . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies.

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.