# Guohui Lin

## Publications Authored By Guohui Lin

The {\em maximum duo-preservation string mapping} ({\sc Max-Duo}) problem is the complement of the well studied {\em minimum common string partition} ({\sc MCSP}) problem, both of which have applications in many fields including text compression and bioinformatics. $k$-{\sc Max-Duo} is the restricted version of {\sc Max-Duo}, where every letter of the alphabet occurs at most $k$ times in each of the strings, which is readily reduced into the well known {\em maximum independent set} ({\sc MIS}) problem on a graph of maximum degree $\Delta \le 6(k-1)$. In particular, $2$-{\sc Max-Duo} can then be approximated arbitrarily close to $1. Read More

We study the {\em maximum duo-preservation string mapping} ({\sc Max-Duo}) problem, which is the complement of the well studied {\em minimum common string partition} ({\sc MCSP}) problem. Both problems have applications in many fields including text compression and bioinformatics. Motivated by an earlier local search algorithm, we present an improved approximation and show that its performance ratio is no greater than ${35}/{12} < 2. Read More

We investigate a single machine rescheduling problem that arises from an unexpected machine unavailability, after the given set of jobs has already been scheduled to minimize the total weighted completion time. Such a disruption is represented as an unavailable time interval and is revealed to the production planner before any job is processed; the production planner wishes to reschedule the jobs to minimize the alteration to the originally planned schedule, which is measured as the maximum time deviation between the original and the new schedules for all the jobs. The objective function in this rescheduling problem is to minimize the sum of the total weighted completion time and the weighted maximum time deviation, under the constraint that the maximum time deviation is bounded above by a given value. Read More

Given a vertex-weighted connected graph $G = (V, E)$, the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree $T$ of $G$ such that the total weight of the internal vertices in $T$ is maximized. The un-weighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio $13/17$. The currently best approximation algorithm for MwIST only has a performance ratio $1/3 - \epsilon$, for any $\epsilon > 0$. Read More

We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. Read More

We investigate the maximum happy vertices (MHV) problem and its complement, the minimum unhappy vertices (MUHV) problem. We first show that the MHV and MUHV problems are a special case of the supermodular and submodular multi-labeling (Sup-ML and Sub-ML) problems, respectively, by re-writing the objective functions as set functions. The convex relaxation on the Lov\'{a}sz extension, originally presented for the submodular multi-partitioning (Sub-MP) problem, can be extended for the Sub-ML problem, thereby proving that the Sub-ML (Sup-ML, respectively) can be approximated within a factor of $2 - \frac{2}{k}$ ($\frac{2}{k}$, respectively). Read More

The general Bandpass-$B$ problem is NP-hard and can be approximated by a reduction into the weighted $B$-set packing problem, with a worst case performance ratio of $O(B^2)$. When $B = 2$, a maximum weight matching gives a 2-approximation to the problem. In this paper, we call the Bandpass-2 problem simply the Bandpass problem. Read More

We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that runs in time $O^{*}(\rho^k)$, where $\rho = \sqrt{\sqrt{2} + 1} \approx 1.555$ is the positive root of the polynomial $x^4-2x^2-1$. Read More