Yinfeng Xu

TCS Journal 2019 Journal Article

On-line scheduling with monotone subsequence constraints

• Kelin Luo
• Yinfeng Xu
• Huili Zhang

In this paper, we study an on-line scheduling problem that is motivated by applications such as carpooling. The ride requests arrive on-line over-list and specify the service locations (among m locations). The goal is to determine a schedule that maximizes the number of satisfied requests using k servers. We consider two variants of the problem with respect to constraints on the service location: in the monotone service direction variant, the service locations of the requests assigned to a server must be monotonic; in the strict monotone service direction variant, the service locations must be strictly monotonic. We present lower bounds on the competitive ratio for both variants. For the monotone service direction variant, we give an optimal straightforward algorithm if k ≥ m and we prove that no deterministic on-line algorithm can achieve a constant competitive ratio if k < m. For the strict monotone service direction variant, we give a lower bound max ⁡ { 2 ( m − 1 ) m, 1 } on the competitive ratio of barely deterministic algorithms if k > 2, and a lower bound of max ⁡ { m 2, 1 } if k ≤ 2. We propose a Balanced Interval Algorithm for the strict monotone service direction variant if k > 2 and report some numerical experiments to evaluate the efficiency of this algorithm.

TCS Journal 2019 Journal Article

The discrete and mixed minimax 2-center problems

• Yi Xu
• Jigen Peng
• Yinfeng Xu
• Binhai Zhu

Letting P be a set of n points in the plane, the discrete minimax 2-center problem ( D M M 2 C P ) is to find two disks centered at { p 1, p 2 } ∈ P that minimize the maximum of two terms, namely, the Euclidean distance between two centers and the distance of any other point to the closer center. The mixed minimax 2-center problem ( M M M 2 C P ) is when one of the two centers is not in P. We present algorithms solving the D M M 2 C P and M M M 2 C P. The time complexities of solving the D M M 2 C P and M M M 2 C P are O ( n 2 log ⁡ n ) and O ( n 2 log 2 ⁡ n ) respectively. Furthermore, we consider two Steiner minimum sum dipolar spanning tree problems, in which one of the two dipoles is a Steiner point and the dipoles are both Steiner points. These two problems are shown to be solvable in O ( n log ⁡ n ) and O ( n ) time respectively.

MFCS Conference 2018 Conference Paper

Car-Sharing between Two Locations: Online Scheduling with Two Servers

• Kelin Luo
• Thomas Erlebach
• Yinfeng Xu

In this paper, we consider an on-line scheduling problem that is motivated by applications such as car sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using two servers (cars). Each ride request specifies the pick-up time and the pick-up location (among two locations, with the other location being the destination). The length of the time interval between the submission of a request (booking time) and the pick-up time is fixed. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted. We present lower bounds on the competitive ratio for this problem and propose a smart greedy algorithm that achieves the best possible competitive ratio.

TCS Journal 2017 Journal Article

An FPTAS for the parallel two-stage flowshop problem

• Jianming Dong
• Weitian Tong
• Taibo Luo
• Xueshi Wang
• Jueliang Hu
• Yinfeng Xu
• Guohui Lin

We consider the NP-hard m-parallel two-stage flowshop problem, abbreviated as the ( m, 2 ) -PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespan, i. e. the maximum completion time of all the jobs on the m flowshops. The ( m, 2 ) -PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomial time dynamic programming algorithm to solve the ( m, 2 ) -PFS problem optimally, for any fixed m, based on an earlier idea for solving the ( 2, 2 ) -PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the ( m, 2 ) -PFS problem.

TCS Journal 2017 Journal Article

Corrigendum to “An FPTAS for the parallel two-stage flowshop problem” [Theoret. Comput. Sci. 657 (2017) 64–72]

• Jianming Dong
• Jueliang Hu
• Mikhail Y. Kovalyov
• Guohui Lin
• Taibo Luo
• Weitian Tong
• Xueshi Wang
• Yinfeng Xu

TCS Journal 2016 Journal Article

The approximation algorithms for a class of multiple-choice problem

• Yin Wang
• Yinfeng Xu

Given a set of n points, which is a unit set of m colored sets, we study the minimum circle to cover one of each colored set at least. In this paper, we study some problems of optimizing some properties of color-spanning set. Firstly, we show a way to find a color-spanning set for each point and constitute a union of color-spanning sets without FCVD (The Farthest Color Voronoi Diagram). The approach to find each color-spanning set is based on the nearest neighbor points which have different colors. For every color-spanning set, we can find a enclosing circle to cover all points of each color-spanning set, which is a good approximate for MDCS (The Minimum Diameter Color-Spanning Set) problem. We propose an approximation algorithm for the SECSC (The Smallest Color-Spanning Circle) problem with 2-factor approximation result. For | P | = n and | Q | = m, the worst running time of our algorithm is O ( n 2 ). Although these results are not as good as previous results with FCVD, the performance of our algorithms in R d is much better than others. Moreover, an approximation algorithm can solve problem of minimum perimeter of the color-spanning set faster with time of O ( n 2 + n m log ⁡ n ) and ratio 6. This result improved the ratio with only a little cost of time complexity. At last, we give an example for the 2-center SECSC problem. A fast computation of 2-center enclosing circle is proposed with time of O ( n 2 ), but the ratio depends on the gap between the nearest distinct colored distance.

TCS Journal 2015 Journal Article

Minimax regret 1-sink location problem in dynamic path networks

• Yuya Higashikawa
• John Augustine
• Siu-Wing Cheng
• Mordecai J. Golin
• Naoki Katoh
• Guanqun Ni
• Bing Su
• Yinfeng Xu

This paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location is defined as the minimum time to complete the evacuation for all supplies (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We propose an O ( n log ⁡ n ) time algorithm for the minimax regret 1-sink location problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.

TCS Journal 2015 Journal Article

Semi-online hierarchical load balancing problem with bounded processing times

• Taibo Luo
• Yinfeng Xu

In this paper, we consider the online hierarchical scheduling problem on two parallel machines, with the objective of maximizing the minimum machine load. Since no competitive algorithm exists for this problem, we consider the semi-online version with bounded processing times, in which the processing times are bounded by an interval [ 1, α ] where α ≥ 1. We prove that no algorithm can have a competitive ratio less than 1 + α and present an optimal algorithm. Moreover, if we further know the sum of jobs' processing times in advance, we prove that no algorithm can have a competitive ratio less than α where 1 ≤ α < 2, and propose an α-competitive algorithm for this case.

TCS Journal 2014 Journal Article

Combinatorial Optimization and Applications

• Peter Widmayer
• Yinfeng Xu
• Binhai Zhu

TCS Journal 2014 Journal Article

Semi-online scheduling with two GoS levels and unit processing time

• Taibo Luo
• Yinfeng Xu
• Li Luo
• Changzheng He

In this paper, we consider two semi-online scheduling problems of parallel machines with two GoS (grade of service) levels and unit processing time, in which the objective is to minimize the makespan. Assume that the GoS levels of the first s machines are 2 and that of the last ( m − s ) machines are 1 where m is the number of machines. The first problem is the lookahead version where an online algorithm is able to foresee the information of the next k jobs. The second problem is the buffer version where a buffer is available for storing at most g jobs. For the both versions, we prove that the lookahead ability or the buffer is useless for designing algorithm when k < m − s or g < min { s, m − s }. We also show that no online algorithm has a competitive ratio less than m 2 m ( m − s ) + s 2 for any constant k or g. Moreover, we present two optimal online algorithms for k = m 2 − 1 s + s − m and g = m − m m ( m − s ) + s 2. At last, for the case with only two machines, we prove that the two algorithms can get their best possible competitive ratio when k = 1 and g = 1.

TCS Journal 2013 Journal Article

Approximation algorithms for parallel machine scheduling with linear deterioration

• Ming Liu
• Feifeng Zheng
• Shijin Wang
• Yinfeng Xu

This paper deals with a parallel machine scheduling problem. Different from fixed processing time assumption in the classical scheduling, a job’s processing time is a simple linear increasing function of its starting time. The aim is makespan minimization, and our focus is on the case with an arbitrary number of parallel machines. We prove that LIST rule is ( 1 + b m a x ) m − 1 m -approximation where m is the number of machines and b m a x is the maximum deteriorating rate of job. We then propose one heuristic LDR (Largest deteriorating Rate first). The heuristic is proved by ( 1 + b m i n ) m − 1 m -approximation where b m i n is the minimum deteriorating rate. We further show that this ratio is tight when m = 2, 3 and 4.

TCS Journal 2012 Journal Article

New results on single-machine scheduling with past-sequence-dependent delivery times

• Ming Liu
• Feifeng Zheng
• Chengbin Chu
• Yinfeng Xu

Scheduling with past-sequence-dependent ( p s d ) delivery times is motivated by questions that arise in the electronic manufacturing industry: an electronic component may be exposed to certain a electromagnetic field while waiting for processing and is required to neutralize the effect of electromagnetism. The time spent on the neutralization process has been modeled as p s d delivery time in the literature. In this paper, we consider single-machine scheduling problems with p s d delivery times. We respectively derive polynomial algorithms for the following objective functions: the minimization of the total weighted completion time, the total weighted discounted completion time, the total absolute differences in completion times and the sum of earliness, tardiness and common due date penalty. At last, for the criteria of minimization the total weighted tardiness, we propose a polynomial algorithm to optimally solve the problem under a certain condition.

TCS Journal 2011 Journal Article

Optimal algorithms for online scheduling on parallel machines to minimize the makespan with a periodic availability constraint

• Ming Liu
• Feifeng Zheng
• Chengbin Chu
• Yinfeng Xu

In this paper we investigate two online scheduling problems. The first one is online scheduling on m parallel machines with one machine periodically unavailable. The second problem is online scheduling on two uniform parallel machines where one machine is periodically unavailable. The online paradigm is that jobs arrive over list, i. e. , when a job presents, we have to irrevocably assign it before the next one is seen. Preemption is not allowed. The objective is to minimize makespan. We suppose that the length of each available period is normalized to 1 and the length of each unavailable period is α > 0. For the first problem, we give an optimal algorithm with competitive ratio 2. For the second problem, we assume that the speed of the periodically unavailable machine is normalized to 1, while the speed of the other one is s > 0. In the case where s ≥ 1, we design an algorithm and show that it is optimal with competitive ratio 1 + 1 s. Then we further give some lower bounds on competitive ratio in the case 0 < s < 1. We also study a special case and prove that L P T algorithm proposed in Xu et al. (2009) [7] is optimal with competitive ratio 3 2.

TCS Journal 2011 Journal Article

Optimal algorithms for the online time series search problem

• Yinfeng Xu
• Wenming Zhang
• Feifeng Zheng

In the problem of online time series search introduced by El-Yaniv et al. (2001) [1], a player observes prices one by one over time and shall select exactly one of the prices on its arrival without the knowledge of future prices, aiming to maximize the selected price. In this paper, we extend the problem by introducing profit function. Considering two cases where the search duration is either known or unknown beforehand, we propose two optimal deterministic algorithms respectively. The models and results in this paper generalize those of El-Yaniv et al. (2001) [1].

TCS Journal 2009 Journal Article

Online scheduling on m uniform machines to minimize total (weighted) completion time

• Ming Liu
• Chengbin Chu
• Yinfeng Xu
• Feifeng Zheng

We study two online problems on m uniform machines with speeds s 1 ≤ ⋯ ≤ s m. The problems are online in the sense that all jobs arrive over time. Each job’s characteristics, such as processing time and weight become known at its arrival time. For the first problem Q | r j, o n l i n e | ∑ C j, we prove that R-LIST algorithm is 4 m − 3 + 3 2 -competitive. For the second problem Q | r j, o n l i n e, p m t n | ∑ w j C j, we show that WSPT-1 algorithm is 2 -competitive if s i / s m ≥ ∑ h = 1 i s h / ∑ h = 1 m s h for i = 1, …, m − 1. Then we study a special case where s 1 = s 2 = ⋯ = s m − 1 ≤ s m. We obtain that algorithm WSPT-1 is 2 -competitive if s m ( m − 2 ) ≤ s 1 ( m − 1 ).

TCS Journal 2009 Journal Article

Online scheduling on two uniform machines to minimize the makespan

• Ming Liu
• Yinfeng Xu
• Chengbin Chu
• Feifeng Zheng

We consider two problems of online scheduling on two uniform machines: online scheduling under a grade of service (GoS) and online scheduling with reassignment. These problems are online in the sense that when a job presents, we have to irrevocably assign it to one of the machines before the next job is seen. The objective is to minimize the makespan. In the first problem, GoS means that some jobs have to be processed by some machine so that they can be guaranteed a higher quality. Assume that the speed of the higher GoS machine is normalized to 1, while the speed of the other one is s. We show that a lower bound of competitive ratio is 1 + 2 s s + 2 in the case 0 < s ≤ 1 and 1 + s + 1 s ( 2 s + 1 ) in the case s > 1. Then we propose and analyze two online algorithms: HSF algorithm and EX-ONLINE algorithm. HSF is optimal in the case where s > 1 and Σ 1 ≥ Σ 2 s, where Σ 1 and Σ 2 denote the total processing time of jobs which request higher GoS machine and the total processing time of jobs which request the normal one, respectively. EX-ONLINE is optimal in the case 2 ( 2 − 1 ) ≤ s ≤ 1. In the second problem, we study two subproblems P L and P A proposed in [Z. Tan, S. Yu, Online scheduling with reassignment, Operations Research Letters 36 (2008) 250–254]. Assume that the speeds of 2 uniform machines are 1 and s ≥ 1, respectively. For P L where we can reassign the last k jobs of the sequence, we show a lower bound of competitive ratio 1 + 1 1 + s. For P A where we can reassign arbitrary k jobs, we show a lower bound of competitive ratio ( s + 1 ) 2 s 2 + s + 1. We propose a s + 1 s -competitive algorithm HSF-1 for both P L and P A. For P A, we propose a ( s + 1 ) 2 s + 2 -competitive algorithm EX-RA, which is superior to HSF-1 when 1 ≤ s ≤ 2.

TCS Journal 2009 Journal Article

Online scheduling to minimize modified total tardiness with an availability constraint

• Ming Liu
• Yinfeng Xu
• Chengbin Chu
• Feifeng Zheng

We consider online scheduling problems to minimize modified total tardiness. The problems are online in the sense that jobs arrive over time. For each job J j, its processing time p j, due date d j and weight w j become known at its arrival time (or release time) r j. Preemption is not allowed. We first show that there is no finite competitive ratio for problem 1 | o n l i n e, r j, d j | ∑ w j T j. So we focus on problem 1 | o n l i n e, r j, d j | ∑ w j ( T j + d j ) and show that D-SWPT (Delayed Shortest Weighted Processing Time) algorithm is 3 -competitive. We further study two problems 1 | o n l i n e, r j, d j, h ( 1 ), r e s | ∑ w j ( T j + d j ) and 1 | o n l i n e, r j, d j, h ( 1 ), N − r e s | ∑ w j ( T j + d j ), where r e s and N − r e s denote resumable and non-resumable models respectively, and h ( 1 ) denotes a non-available time interval [ s, α s ] with s > 0 and α ≥ 1. We give a lower bound of 1 + α for both problems and prove that M − D − S W P T (Modified D-SWPT) is 3 α and 6 α -competitive in the resumable and non-resumable models, respectively. Moreover, we extend the upper bounds to the scenario of parallel machine scheduling with uniform job weight and an assumption that all machines have the same non-available time interval [ s, α s ]. A lower bound of min { α, 1 + α m } is given as well for the scenario.

TCS Journal 2007 Journal Article

Triangulating a convex polygon with fewer number of non-standard bars

• Yinfeng Xu
• Wenqiang Dai
• Naoki Katoh
• Makoto Ohsaki

For a given convex polygon with inner angle no less than 2 3 π and boundary edge bounded by [ l, α l ] for 1 ≤ α ≤ 1. 4, where l is a given standard bar’s length, we investigate the problem of triangulating the polygon using some Steiner points such that (i) the length of each edge in triangulation is bounded by [ β l, 2 l ], where β is a given constant and meets 0 < β ≤ 1 2, and (ii) the number of non-standard bars in the triangulation is minimum. This problem is motivated by practical applications and has not been studied previously. In this paper, we present a heuristic to solve the above problem, which is based on the heuristic to generate a triangular mesh with less number of non-standard bars and shorter maximal edge length, and a process to make the length of each edge lower bounded. Our procedure is simple and easily implemented for this problem, and we prove that it has good performance guaranteed.

TCS Journal 2006 Journal Article

On the edge l ∞ radius of Saitou and Nei's method for phylogenetic reconstruction

• Wenqiang Dai
• Yinfeng Xu
• Binhai Zhu

In this paper, we study the performance of Saitou and Nei's neighbor-joining method for phylogenetic reconstruction. We show that the edge l ∞ radius of the method is 1 4. This improves an result by Atteson [The performance of neighbor-joining methods of phylogenetic reconstruction, Algorithmica 25 (1999) 251–278] and Xu et al. [A lower bound on the edge l ∞ radius of Saitou and Nei's method for phylogenetic reconstruction, Inform. Process. Lett. 94(5) (2005) 225–230]. Previously, only an upper bound 1 4 and a lower bound 1 6 were known.

TCS Journal 2006 Journal Article

Preface

• Nimrod Megiddo
• Yinfeng Xu
• Binhai Zhu

TCS Journal 2002 Journal Article

Approximating uniform triangular meshes in polygons

• Franz Aurenhammer
• Naoki Katoh
• Hiromichi Kojima
• Makoto Ohsaki
• Yinfeng Xu

We consider the problem of triangulating a convex polygon using n Steiner points under the following optimality criteria: (1) minimizing the overall edge length ratio; (2) minimizing the maximum edge length; and (3) minimizing the maximum triangle perimeter. We establish a relation of these problems to a certain extreme packing problem. Based on this relationship, we develop a heuristic producing constant approximations for all the optimality criteria above (provided n is chosen sufficiently large). That is, the produced triangular mesh is uniform in these respects. The method is easy to implement and runs in O(n2 log n) time and O(n) space. The observed runtime is much less. Moreover, for criterion (1) the method works—within the same complexity and approximation bounds—for arbitrary polygons with possible holes, and for criteria (2) and (3) it does so for a large subclass.