Query：
学者姓名：徐寅峰
Refining：
Year
Type
Indexed by
Source
Complex
Co-Author
Language
Clean All
Abstract ：
Motivated by the need for a more sensitive server assignment strategy in supply-chain network management, our total cost comprises coverage area (i.e., disk) sizes and "moving" service modes that facilitate multiple and flexible demand ful-fillment. Selection of k color-spanning centers to achieve cost minimization is the aim of our k-Connected Location Set Cover Problem with Color-spanning Constraint (k-CLSCPCC). The cost reflects the sum of the radii of the color-spanning disks plus the cost of connecting to disk regions. The farthest-color Voronoi diagram(FCVD) helps to assign an individual radius to each selected color-spanning center with aims to minimal cost. The main idea behind our greedy algorithm, which integrates the ideas of the classical minimum-power coverage problem and k-maximum coverage problem, is to minimize the measurable gap between the cost of connecting all nodes and the reduced cost of coverage with k disks. Our proposed algorithm can approximate a 3.368-factor solution within O(n(2)m log m) running time, equal to time cost of generating FCVD, where n is the number of input nodes and m is the number of demand types.
Keyword ：
Color-spanning set Maximum coverage problems Minimum spanning tree Approximation algorithm Farthest-Color Voronoi Diagram(FCVD)
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Wang, Yin , Xu, Yinfeng . An Approximation Algorithm for the k-Connected Location Set Cover Problem with Color-Spanning Constraint [C] . 2021 : 317-325 . |
MLA | Wang, Yin 等. "An Approximation Algorithm for the k-Connected Location Set Cover Problem with Color-Spanning Constraint" . (2021) : 317-325 . |
APA | Wang, Yin , Xu, Yinfeng . An Approximation Algorithm for the k-Connected Location Set Cover Problem with Color-Spanning Constraint . (2021) : 317-325 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
We consider an online car-sharing problem between two locations with advance bookings. Each customer submits a pair of requests, where each request specifies the pick-up time and the pick-up location: one request fromAtoB, and the other request fromBtoA, not necessary in this order. The scheduler aims to maximize the number of satisfied customers, where the schedule has to decide whether or not to accept a request pair immediately at the time when the request pair is submitted. This problem is calledOnlineTransfersForCommuting. We present lower bounds on the competitive ratio for this problem with both fixed booking times and variable booking times, and propose two algorithms, greedy algorithm and balanced greedy algorithm, that achieve the best possible competitive ratios.
Keyword ：
Car-sharing problem Request pairs Online scheduling Competitive analysis
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Luo, Kelin , Xu, Yinfeng , Liu, Haodong . Online scheduling of car-sharing request pairs between two locations [J]. | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2020 . |
MLA | Luo, Kelin 等. "Online scheduling of car-sharing request pairs between two locations" . | JOURNAL OF COMBINATORIAL OPTIMIZATION (2020) . |
APA | Luo, Kelin , Xu, Yinfeng , Liu, Haodong . Online scheduling of car-sharing request pairs between two locations . | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2020 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
Despite the emphases on computability issues in research of algorithmic game theory, the limited computational capacity of players have received far less attention. This work examines how different levels of players’ computational ability (or 'rationality') impact the outcomes of sequential scheduling games. Surprisingly, our results show that a lower level of rationality of players may lead to better equilibria. More specifically, we characterize the sequential price of anarchy (SPoA) under two different models of bounded rationality, namely, players with k-lookahead and simple-minded players. The model in which players have k-lookahead interpolates between the 'perfect rationality' (k= n- 1 ) and 'online greedy' (k= 0 ). Our results show that the inefficiency of equilibria (SPoA) increases in k the degree of lookahead: SPoA = O(k2) for two machines and SPoA = O(2kmin { mk, n} ) for m machines, where n is the number of players. Moreover, when players are simple-minded, the SPoA is exactly m, which coincides with the performance of 'online greedy'. © 2020, Springer Nature Switzerland AG.
Keyword ：
Scheduling Computation theory Game theory
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Chen, Cong , Xu, Yinfeng . The Curse of Rationality in Sequential Scheduling Games [C] . 2020 : 295-308 . |
MLA | Chen, Cong 等. "The Curse of Rationality in Sequential Scheduling Games" . (2020) : 295-308 . |
APA | Chen, Cong , Xu, Yinfeng . The Curse of Rationality in Sequential Scheduling Games . (2020) : 295-308 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
This paper studies the online machine minimization problem, where the jobs have real release times, uniform processing times and a common deadline. We investigate how the lookahead ability improves the performance of online algorithms. Two lookahead models are studied, that is, theadditive lookaheadand themultiplicative lookahead. At any timet, the online algorithm knows all the jobs to be released before time t + L (or beta center dot t) in the additive (or multiplicative) lookahead model. We propose a e/alpha(e-1)+1-competitive online algorithm with the additive lookahead, where alpha = L/T <= 1 and T is the common deadline of the jobs. For the multiplicative lookahead, we provide an online algorithm with a competitive ratio of beta e/(beta-1)e+1, where beta >= 1. Lower bounds are also provided for both of the two models, which show that our algorithms are optimal for two extreme cases, that is, alpha = 0 (or beta = 1) and alpha = 1 (or beta -> infinity), and remain a small gap for the cases in between. Particularly, for alpha = 0 (or beta = 1), the competitive ratio ise, which corresponds to the problem without lookahead. For alpha = 1 (or beta -> infinity), the competitive ratio is 1, which corresponds to the offline version (with full information).
Keyword ：
Lookahead Online machine minimization Online scheduling Online algorithm
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Chen, Cong , Zhang, Huili , Xu, Yinfeng . Online machine minimization with lookahead [J]. | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2020 . |
MLA | Chen, Cong 等. "Online machine minimization with lookahead" . | JOURNAL OF COMBINATORIAL OPTIMIZATION (2020) . |
APA | Chen, Cong , Zhang, Huili , Xu, Yinfeng . Online machine minimization with lookahead . | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2020 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
A long distance link may cause high data latency in cloud computing systems, and thus a computing task may be processed faster by nearby servers than distant servers. To address this class of job (task) scheduling problems, we propose the favorite machine model. Specifically, we are interested in the online version where jobs arrive one by one and must be allocated irrevocably upon each arrival without knowing the future jobs. The objective is to design efficient online algorithms for allocating jobs in order to minimize the makespan. Theoretical performance guarantees are presented for the GREEDY algorithm and the ASSIGN-U algorithm, where the latter is shown to be the best-possible online algorithm for this problem. Our theoretical results generalize the results for several classical problems, e.g. the unrelated machines and the identical machines. We also study a restriction of the model, called the symmetric favorite machine model. A 2.675-competitive algorithm is developed and proved to be the best-possible algorithm for the two machines case. Moreover, computational results show that the algorithms perform quite well for random instances, and reveal some insights for choosing algorithms for practical applications. (C) 2019 Elsevier Ltd. All rights reserved.
Keyword ：
Unrelated machines Competitive ratio Favorite machines Online scheduling Scheduling
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Chen, Cong , Penna, Paolo , Xu, Yinfeng . Online scheduling of jobs with favorite machines [J]. | COMPUTERS & OPERATIONS RESEARCH , 2020 , 116 . |
MLA | Chen, Cong 等. "Online scheduling of jobs with favorite machines" . | COMPUTERS & OPERATIONS RESEARCH 116 (2020) . |
APA | Chen, Cong , Penna, Paolo , Xu, Yinfeng . Online scheduling of jobs with favorite machines . | COMPUTERS & OPERATIONS RESEARCH , 2020 , 116 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
This paper studies the favorite machine model, where each machine has different speed for different types of jobs. The model is a natural generalization of the two related machines model and captures the features of some real life problems, such as the CPU–GPU task scheduling, the two products scheduling and the cloud computing task scheduling. We are interested in the game-theoretic version of the scheduling problem in which jobs correspond to self-interested users and machines correspond to resources. The goal is to design coordination mechanisms (local policies) with a small price of anarchy (PoA) for the scheduling game of favorite machines. We first analyze the well known Makespan policy for our problem, and provide exact bounds on both the PoA and the strong PoA (SPoA). We also propose a new local policy, called FF-LPT, which outperforms several classical policies (e.g., LPT, SPT, FF-SPT and Makespan) in terms of the PoA, and guarantees fast convergence to a pure Nash equilibrium. Moreover, computational results show that the FF-LPT policy also dominates other policies for random instances, and reveal some insights for practical applications. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
Keyword ：
Multitasking Scheduling algorithms Game theory Scheduling
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Chen, Cong , Xu, Yinfeng . Coordination mechanisms for scheduling selfish jobs with favorite machines [J]. | Journal of Combinatorial Optimization , 2020 , 40 (2) : 333-365 . |
MLA | Chen, Cong 等. "Coordination mechanisms for scheduling selfish jobs with favorite machines" . | Journal of Combinatorial Optimization 40 . 2 (2020) : 333-365 . |
APA | Chen, Cong , Xu, Yinfeng . Coordination mechanisms for scheduling selfish jobs with favorite machines . | Journal of Combinatorial Optimization , 2020 , 40 (2) , 333-365 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
Letting . P be a set of . n points in the plane, the discrete minimax 2-center problem (DMM2CP) is to find two disks centered at . (p1,p2)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 (MMM2CP) is when one of the two centers is not in . P. We present algorithms solving the . DMM2CP and . MMM2CP. The time complexities of solving the . DMM2CP and . MMM2CP are . O(n2logn) and . O(n2log2n) 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(nlogn) and . O(n) time respectively. © 2016 Elsevier B.V.
Keyword ：
2-center problem Euclidean distance Facility location problem Spanning tree problems Steiner Steiner points Time complexity Voronoi diagrams
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Xu, Yi , Peng, Jigen , Xu, Yinfeng et al. The discrete and mixed minimax 2-center problems [J]. | Theoretical Computer Science , 2019 , 774 : 95-102 . |
MLA | Xu, Yi et al. "The discrete and mixed minimax 2-center problems" . | Theoretical Computer Science 774 (2019) : 95-102 . |
APA | Xu, Yi , Peng, Jigen , Xu, Yinfeng , Zhu, Binhai . The discrete and mixed minimax 2-center problems . | Theoretical Computer Science , 2019 , 774 , 95-102 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
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{[Formula presented],1} on the competitive ratio of barely deterministic algorithms if k>2, and a lower bound of max{[Formula presented],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. © 2018 Elsevier B.V.
Keyword ：
Competitive analysis Competitive ratio Deterministic algorithms Interval algorithms Monotone subsequence Numerical experiments On-line algorithms Online scheduling
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Luo, Kelin , Xu, Yinfeng , Zhang, Huili . On-line scheduling with monotone subsequence constraints [J]. | Theoretical Computer Science , 2019 , 786 : 13-25 . |
MLA | Luo, Kelin et al. "On-line scheduling with monotone subsequence constraints" . | Theoretical Computer Science 786 (2019) : 13-25 . |
APA | Luo, Kelin , Xu, Yinfeng , Zhang, Huili . On-line scheduling with monotone subsequence constraints . | Theoretical Computer Science , 2019 , 786 , 13-25 . |
Export to | NoteExpress RIS BibTex |
Abstract ：
This paper studies an online over-list model of the makespan minimization in MapReduce-like systems with unsplit map tasks. In this paper, we assume that each job has k map tasks. We study two cases: the first is that each job has only one reduce task which cannot be divided; the second is that each job has one reduce task which can be divided into a series of reduce task parts based on its input. For the first case, we propose a \left(2-\frac{1}{h}\right)-competitive algorithm, and prove the algorithm is optimal, where h is the number of machines. For the second case, we prove that any algorithm has a competitive ratio at least 2- \frac{1}{\beta h}, where \beta is the minimax ratio between the processing time of those reduce task parts from reduce task RJ which are assigned in machine i and the processing time of the reduce task RJ for arbitrary i and j, \beta\leq \frac{\lceil\frac{k}{2}\rceil}{k-1}. We then present an optimal algorithm. © 2019 IEEE.
Keyword ：
Scheduling Optimization Scheduling algorithms Online systems
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Pan, Jiayin , Xu, Yinfeng . Online makespan minimization in MapReduce-like systems with unsplit map tasks [C] . 2019 . |
MLA | Pan, Jiayin et al. "Online makespan minimization in MapReduce-like systems with unsplit map tasks" . (2019) . |
APA | Pan, Jiayin , Xu, Yinfeng . Online makespan minimization in MapReduce-like systems with unsplit map tasks . (2019) . |
Export to | NoteExpress RIS BibTex |
Abstract ：
This paper studies an online over-list model of the makespan minimization in MapReduce-like systems with unsplit map tasks. In this paper, we assume that each job has k map tasks. We study two cases: the first is that each job has only one reduce task which cannot be divided; the second is that each job has one reduce task which can be divided into a series of reduce task parts based on its input. For the first case, we propose a (2 - 1/h)-competitive algorithm, and prove the algorithm is optimal, where h is the number of machines. For the second case, we prove that any algorithm has a competitive ratio at least 2 - 1/beta h, where beta is the minimax ratio between the processing time of those reduce task parts from reduce task R-j which are assigned in machine i and the processing time of the reduce task R-j, for arbitrary i and j, beta <= inverted right perpendiculark/2inverted right perpendicular/k-1. We then present an optimal algorithm.
Keyword ：
MapReduce Online algorithm Scheduling
Cite：
Copy from the list or Export to your reference management。
GB/T 7714 | Pan, Jiayin , Xu, Yinfeng . Online makespan minimization in MapReduce-like systems with unsplit map tasks [C] . 2019 : 470-475 . |
MLA | Pan, Jiayin et al. "Online makespan minimization in MapReduce-like systems with unsplit map tasks" . (2019) : 470-475 . |
APA | Pan, Jiayin , Xu, Yinfeng . Online makespan minimization in MapReduce-like systems with unsplit map tasks . (2019) : 470-475 . |
Export to | NoteExpress RIS BibTex |
Export
Results： |
Selected to |
Format： |