Query：
学者姓名：徐寅峰
Refining：
Year
Type
Indexed by
Source
Complex
Co-Author
Language
Clean All
Abstract ：
In recent years, advanced information communication technology (such as beyond 5G and 6G) will enable convenient end-to-end communication. This would allow collections of individual preferences as predictions of travellers' perceptions, and thus support data analysis and traffic control in a dynamic circumstance. Therefore, analysis of nonlinearly modelled perceptions and perception-based user equilibrium are the necessary problem we encounter. This research explores the existence characteristics of perception-based stochastic user equilibrium (P-SUE), a type of stochastic user equilibrium where travelers make route choices according to their perceptive traffic circumstances instead of actual ones. A nonlinear perception model with stochasticity is developed and the traffic arrivals are approximately transformed from Poisson-distributed to Normal-distributed. From a static perspective, we develop a P-SUE model with a heterogeneous traveler community and discuss the interaction among travelers' attitude, grouping and static perception-based stochastic user equilibrium (P-SSUE). After embedding a day-to-day learning process into the P-SSUE model, we further explore evolutionary dynamics of the equilibrium. Several scenarios are provided to investigate effects and sensitivity of traveler-related and road-related factors. It is found that learning produces perturbation and makes the existence condition of P-SSUE more complicated; the convergence processes of P-SSUEs are significantly shortened as the learning rate increases to higher than 0.1.
Keyword ：
6G Analytical models learning process perception Predictive models Process control Roads route choice Stability analysis Stochastic processes Sun traffic flow user equilibrium
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Sun, Jingchun , Deng, Fei , Fu, Haoran et al. An Evolutionary Game of Perception-Based Stochastic User-Equilibrium in a Parallel Network [J]. | IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS , 2022 . |
| MLA | Sun, Jingchun et al. "An Evolutionary Game of Perception-Based Stochastic User-Equilibrium in a Parallel Network" . | IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS (2022) . |
| APA | Sun, Jingchun , Deng, Fei , Fu, Haoran , Xu, Yinfeng . An Evolutionary Game of Perception-Based Stochastic User-Equilibrium in a Parallel Network . | IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS , 2022 . |
| Export to | NoteExpress RIS BibTex |
Abstract ：
We study risk hedging in the online procurement problem, where one buyer and one seller sign reservation contracts in advance to hedge against the risks from the uncertainties of real demand and spot price. We generalize the traditional two-stage procurement model such that the buyer has the flexibility of signing multiple contracts in the first stage and makes decision on executions in the second stage. A lower bound on the performance of any deterministic algorithms is presented by restricting the possible execution price sequence and real demand in worst case. Then a deterministic online algorithm called Price Look Back (PLB) is designed with a competitive ratio that tends to the lower bound if historical execution prices are less fluctuant. Extensive experiments are conducted on both synthetic and real-life instances to evaluate the practical performance of PLB. The experimental results show that PLB performs significantly better than its (worst-case) theoretical guarantee in most instances. In addition, PLB is robust with respect to inaccurate information learned from the historical data. Specifically, the average extra cost incurred by the inaccurate information can be around 5% in real-life instances.
Keyword ：
Combinatorial optimization Demand uncertainty Operations strategy Procurement Risk management
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Wang, Sizhe , Zhang, Huili , Xu, Yinfeng et al. Online procurement problem with risk hedging [J]. | COMPUTERS & INDUSTRIAL ENGINEERING , 2022 , 164 . |
| MLA | Wang, Sizhe et al. "Online procurement problem with risk hedging" . | COMPUTERS & INDUSTRIAL ENGINEERING 164 (2022) . |
| APA | Wang, Sizhe , Zhang, Huili , Xu, Yinfeng , Tong, Weitian . Online procurement problem with risk hedging . | COMPUTERS & INDUSTRIAL ENGINEERING , 2022 , 164 . |
| Export to | NoteExpress RIS BibTex |
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 ：
Approximation algorithm Color-spanning set Farthest-Color Voronoi Diagram(FCVD) Maximum coverage problems Minimum spanning tree
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 et al. "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 ：
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 ：
Computation theory Game theory Scheduling
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 et al. "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 algorithm Online machine minimization Online scheduling
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 , 43 (5) : 1149-1172 . |
| MLA | Chen, Cong et al. "Online machine minimization with lookahead" . | JOURNAL OF COMBINATORIAL OPTIMIZATION 43 . 5 (2020) : 1149-1172 . |
| APA | Chen, Cong , Zhang, Huili , Xu, Yinfeng . Online machine minimization with lookahead . | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2020 , 43 (5) , 1149-1172 . |
| 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 ：
Competitive ratio Favorite machines Online scheduling Scheduling Unrelated machines
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 et al. "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 ：
Game theory Multitasking Scheduling Scheduling algorithms
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 et al. "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 ：
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 Competitive analysis Online scheduling Request pairs
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 , 43 (5) : 1240-1263 . |
| MLA | Luo, Kelin et al. "Online scheduling of car-sharing request pairs between two locations" . | JOURNAL OF COMBINATORIAL OPTIMIZATION 43 . 5 (2020) : 1240-1263 . |
| APA | Luo, Kelin , Xu, Yinfeng , Liu, Haodong . Online scheduling of car-sharing request pairs between two locations . | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2020 , 43 (5) , 1240-1263 . |
| 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 |
Export
| Results： |
Selected to |
| Format： |
