Search

In plenty of data analysis tasks, a basic and time-consuming process is to produce a large number of solutions and feed them into downstream processing. Various enumeration algorithms have been developed for this purpose. An enumeration algorithm produces all solutions of a problem instance without repetition. To be a statistically meaningful representation of the solution space, solutions are required to be enumerated in uniformly random order. This paper studies a set of self-reducible NP-problems in three hierarchies, where the problems are polynomially countable ($Sr_{NP}^{FP}$), admit FPTAS ($Sr_{NP}^{FPTAS}$), and admit FPRAS ($Sr_{NP}^{FPRAS}$), respectively. The trivial algorithm based on a (almost) uniform generator is in fact inefficient. We provide a new insight that the (almost) uniform generator is not the end of the story. More efficient algorithmic frameworks are proposed to enumerate solutions in uniformly random order for problems in these three hierarchies. (1) For problems in $Sr_{NP}^{FP}$, we show a random-order enumeration algorithm with polynomial delay (PDREnum); (2) For problems in $Sr_{NP}^{FPTAS}$, we show a Las Vegas random-order enumeration algorithm with expected polynomial delay (PDLVREnum); (3) For problems in $Sr_{NP}^{FPRAS}$, we devise a fully polynomial delay Atlantic City random-order enumeration algorithm with expected delay polynomial in the input size and the given error probability $\delta$ (FPACREnum), which has a probability of at least $1-\delta$ becoming a Las Vegas random-order enumeration algorithm. Finally, to further improve the efficiency of the random-order enumeration algorithms, based on the master/slave paradigm, we present a parallelization with 1.5-optimal enumeration delay and running time, along with the theoretical analysis.

Various new scheduling problems have been arising from practical production processes and spawning new research areas in the scheduling field. We study the parallel multi-stage open shops problem, which generalizes the classic open shop scheduling and parallel machine scheduling problems. Given m identical k-stage open shops and a set of n jobs, we aim to process all jobs on these open shops with the minimum makespan, i.e., the completion time of the last job, under the constraint that job preemption is not allowed. We present an efficient polynomial-time approximation scheme (EPTAS) for the case when both m and k are constant. The main idea for our EPTAS is the combination of several categorization, scaling, and linear programming rounding techniques. Jobs and/or operations are first scaled and then categorized carefully into multiple types so that different types of jobs and/or operations are scheduled appropriately without increasing the makespan too much.

As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, which was motivated by applications in cloud computing and introduced by Chen et al. [3] recently. A set of two-stage jobs are selected and scheduled on parallel two-stage flowshops to achieve the maximum total profit while maintaining the given makespan constraint. We give a positive answer to an open question about its approximability proposed by Chen et al. [3]. More specifically, based on guessing strategies and rounding techniques for linear programs, we present a polynomial-time approximation scheme (PTAS) for the case when the number of flowshops is a fixed constant., Comment: Theoretical Computer Science (2022)

Given a graph $G = (V, E)$, the $3$-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most $3$ to cover all the vertices of $V$. It is different from but closely related to the well-known $3$-set cover problem. The best known approximation algorithm for the $3$-path partition problem was proposed recently and has a ratio $13/9$. Here we present a local search algorithm and show, by an amortized analysis, that it is a $4/3$-approximation. This ratio matches up to the best approximation ratio for the $3$-set cover problem., Comment: 16 pages, 21 figures

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. To avoid machine breakdown, one should guarantee a non-negative maintenance level at any time point; and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance activities such that the total completion time of jobs is minimized. There are two variants of maintenance activities: in the partial maintenance case each activity can be allocated to increase the machine maintenance level to any level not exceeding the maximum; in the full maintenance case every activity must be allocated to increase the machine maintenance level to the maximum. In a recent work, the problem in the full maintenance case has been proven NP-hard; several special cases of the problem in the partial maintenance case were shown solvable in polynomial time, but the complexity of the general problem is left open. In this paper we first prove that the problem in the partial maintenance case is NP-hard, thus settling the open problem; we then design a $2$-approximation algorithm., Comment: 15 pages

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. The Bandpass problem can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present a ${426}{227}$-approximation algorithm for the problem. Such an improved approximation is built on an intrinsic structural property proven for the optimal solution and several novel schemes to partition a $b$-matching into desired matchings.

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$. This improves the current-best algorithm of Chen et al. that runs in time $O^{*}(1.619^k)$. For the {\sc generalized multiway cut on trees} problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the {\sc generalized multiway cut on trees} problem to the {\sc multicut on trees} problem, our results give a parameterized algorithm that solves the {\sc generalized multiway cut on trees} problem in time $O^{*}(\rho^k)$, where $\rho = \sqrt{\sqrt{2} + 1} \approx 1.555$ time.