Search

In this paper, we address the problem of online car-sharing with variable booking times (CSV for short). In this scenario, customers submit ride requests, each specifying two important time parameters: the booking time and the pick-up time (start time), as well as two location parameters—the pick-up location and the drop-off location within a graph. For each request, it’s important to note that it must be booked before its scheduled start time. The booking time can fall within a specific interval prior to the request’s starting time. Additionally, each car is capable of serving only one request at any given time. The primary objective of the scheduler is to optimize the utilization of k cars to serve as many requests as possible. As requests arrive at their booking times, the scheduler faces an immediate decision: whether to accept or decline the request. This decision must be made promptly upon request submission, precisely at the booking time. We prove that no deterministic online algorithm can achieve a competitive ratio smaller than L + 1 even on a special case of a path (where L denotes the ratio between the largest and the smallest request travel time). For general graphs, we give a Greedy Algorithm that achieves (3 L + 1) -competitive ratio for CSV. We also give a Parted Greedy Algorithm with competitive ratio (5 2 L + 10) when the number of cars k is no less than 5 4 L + 20 ; for CSV on a special case of a path, the competitive ratio of Parted Greedy Algorithm is (2 L + 10) when k ≥ L + 20 . [ABSTRACT FROM AUTHOR]

Liquid droplets hanging from solid surfaces are commonplace, but their physics is complex. Examples include dew or raindrops hanging onto wires or droplets accumulating onto a cover placed over warm food or windshields. In these scenarios, determining the force of detachment is crucial to rationally design technologies. Despite much research, a quantitative theoretical framework for detachment force remains elusive. In response, we interrogated the elemental droplet–surface system via comprehensive laboratory and computational experiments. The results reveal that the Young–Laplace equation can be utilized to accurately predict the droplet detachment force. When challenged against experiments with liquids of varying properties and droplet sizes, detaching from smooth and microtextured surfaces of wetting and non-wetting chemical make-ups, the predictions were in an excellent quantitative agreement. This study advances the current understanding of droplet physics and will contribute to the rational development of technologies. Understanding the physics that govern the dynamics of liquid droplets and their interaction with solid surfaces is crucial for a range of industrial applications, from pesticides to solar cells. Here, the authors develop a framework based on the Young-Laplace equation, to predict the force required to detach a drop from flat and microstructured solid surfaces. [ABSTRACT FROM AUTHOR]

In this work, we investigate a berth allocation game involving m identical berths and n vessels. Each vessel selfishly selects a consecutive set of berths for unloading, with the objective of minimizing its own cost represented by the maximum load among the chosen berths. The social cost is defined as the makespan, i.e., the maximum load over all berths. Our game generalizes classical machine scheduling games where jobs (vessels) may require multiple consecutive machines (berths). We analyze the price of anarchy (PoA) of the berth allocation game, which quantifies the impact of selfish behaviors of vessels. Specifically, we first consider a special case where each job can occupy at most two consecutive machines, and derive exact upper and lower bounds for the PoA based on the number of machines m. We show that the PoA asymptotically approaches 9 4 . For the general case where each job can occupy an arbitrary number of consecutive machines, we obtain a tight bound for the PoA, which is Θ log m log log m . [ABSTRACT FROM AUTHOR]

Inspired by the applications in on-demand manufacturing, we introduce the online k-color spanning disk problem, the first online model for color spanning problems to the best of our knowledge. Given a set P of n colored points in a plane, with each color chosen from a set C of m ≤ n colors, the online k-color spanning disk problem determines the location of the center that minimizes the accumulated radius of the minimum spanning disks for a sequence of color sets, denoted by δ = ⟨ C 1 , C 2 , … , C T ⟩ , C t ⊆ C , | C t | ≥ k , t ∈ { 1 , 2 , … , T } , as they are presented online. Here, a minimum spanning disk for a color set means a disk contains at least one point of each color. We construct a special instance to establish a lower bound on the performance of any online algorithms. Then, an O (n m log n) -time Voronoi-diagram-based algorithm is designed such that its competitive ratio matches the problem’s lower bound. This implies our algorithm is theoretically the best possible in terms of the competitive ratio. We also introduce and study a variant, named the online balanced k-color spanning disk problem, for which a non-trivial lower bound and a best possible algorithm are presented. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the concept of "workload fence" into online machine rental and machine scheduling problems. With the knowledge of workload fence, online algorithms acquire the information of a finite number of first released jobs in advance. The concept originates from the frozen time fence in the domain of master scheduling in materials management. The total processing time of the jobs foreseen, corresponding to a finite number of jobs, is called workload fence, which is irrelevant to the job sequence. The remaining jobs in the sequence, however, can only become known on their arrival. This work aims to reveal whether the knowledge of workload fence helps to boost the competitive performance of deterministic online algorithms. For the online machine rental problem, we prove that the competitiveness of online algorithms can be improved with a sufficiently large workload fence. We further propose a best online algorithm for the corresponding scenario. For online parallel machine scheduling with workload fence, we give a positive answer to the above question for the case where the workload fence is equal to the length of the longest job. We also show that the competitiveness of online algorithms may not be improved even with a workload fence strictly larger than the largest length of a job. The results help one manager to make a better decision regarding the tradeoff between the performance improvement of online algorithms and the cost caused to acquire the knowledge of workload fence. [ABSTRACT FROM AUTHOR]

This paper addresses the online parallel machine scheduling problem with machine leasing discount. Rental cost discount is a common phenomenon in the sharing manufacturing environment. In this problem, jobs arrive one by one over-list and must be allocated irrevocably upon their arrivals without knowing future jobs. Each job is with one unit of processing time. One manufacturer leases a limited number of identical machines over a manufacturing resource sharing platform, and pays a rental fee of α per time unit for processing jobs. Especially, when the time duration of a leasing machine reaches the discount time point, the manufacturer will get a discount for further processing jobs on the machine, i.e., the unit time rental cost is α β , where β = 1 / 2 is the discount coefficient. The objective function is the sum of makespan and the rental cost of all the sharing machines. When the unit time rental cost α ≥ 2 , we first provide the lower bound of objective value of an optimal schedule in the offline version and prove a lower bound of 1.093 for the problem. Based on the analysis of the offline solution, we present a deterministic online algorithm LS-RD with a tight competitive ratio of 3/2. When 1 ≤ α < 2 , we prove that the competitive ratios of algorithm LIST are 1 and 2 for the case of m = 2 and m → ∞ , respectively. For the general rental discount 0 < β ≤ 1 , we give the relevant results for offline and online solutions. [ABSTRACT FROM AUTHOR]

This work studies the problem of cross-docking truck scheduling introduced by (Int J Prod Econ 194:102–112, Serrano et al. 2017), where internal operations including repacking and storing operations are considered. The objective is to minimize the number of inbound trucks which are assigned beyond their contracted time windows. For the special case where only inbound truck arrivals are considered while the outbound truck departures are not ensured, we present some properties of the model and propose a heuristic algorithm called Light Period and Less Options (LPLO) to solve it. For the general case of the problem, due to its NP-hardness, we design a non-trivial Three-phase Greedy (TG) algorithm and the Genetic algorithm (GA). Experimental results with comparison between exact solutions by the CPLEX solver and solutions by the two heuristic algorithms demonstrate that the both proposed heuristic algorithms are of high efficiency in generating optimal or nearly optimal solutions for the considered problem in this work. [ABSTRACT FROM AUTHOR]

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, the additive lookahead and the multiplicative lookahead. At any time t, the online algorithm knows all the jobs to be released before time t + L (or β · t ) in the additive (or multiplicative) lookahead model. We propose a e α (e - 1) + 1 -competitive online algorithm with the additive lookahead, where α = 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 β e (β - 1) e + 1 , where β ≥ 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, α = 0 (or β = 1 ) and α = 1 (or β → ∞ ), and remain a small gap for the cases in between. Particularly, for α = 0 (or β = 1 ), the competitive ratio is e, which corresponds to the problem without lookahead. For α = 1 (or β → ∞ ), the competitive ratio is 1, which corresponds to the offline version (with full information). [ABSTRACT FROM AUTHOR]

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 from A to B, and the other request from B to A, 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 called OnlineTransfersForCommuting. 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. [ABSTRACT FROM AUTHOR]

Acquiring a comprehensive and accurate understanding of habitat preference is essential for species conservation and fishery management, especially for mobile species that migrate seasonally. Presence and absence data from field surveys are recommended when available due to their high reliability. Using field survey data, we investigated seasonal habitat suitability requirements for Tanaka's snailfish (Liparis tanakae) in the Bohai Sea and Yellow Sea (BSYS) via a machine-learning method, random forests (RFs). Five environmental and biologically relevant variables (bottom temperature, bottom salinity, current velocity, depth and distance to shore) were used to build the ecological niches between the presence/absence data and suitable habitat. In addition, the degree to which false absence data might impact model performance was evaluated. Our results indicated that RFs provided accurate predictions, with seasonal habitat suitability maps of L. tanakae differing substantially. Bottom temperature and salinity were identified as important factors influencing the distribution of L. tanakae. False absence data were found to have negative effects on model performance and the decrease in evaluation metrics was usually significant (P<0.05) after 30% or more errors were added to the absence data. Through identifying highly suitable areas within its geographic range, our study provides a baseline for L. tanakae that can be further applied in ecosystem modelling and fishery management in the BSYS. [ABSTRACT FROM AUTHOR]

In this paper, we consider the k-sink location problem in a path network with the goal of optimizing a combinational function of the maximum completion time and the total completion time. Let P = V , E be an undirected path network with n vertices. Each vertex has a positive weight, indicating the initial amount of supplies, and each edge has a positive length and a uniform capacity, which is the maximum amount of supplies that can enter the edge per unit time. Our goal is to identify k sink locations on the path P so that all supplies will be successfully evacuated and the given objective function is optimized. This paper presents two efficient polynomial time algorithms, which achieve O n for k = 1 and O n 6 for general k, respectively. [ABSTRACT FROM AUTHOR]

Operation management of automated storage and retrieval system (AS/RS) has a great impact on system performance and is a hot research topic. Most existing works for AS/RS operation management address determining storage and retrieval (S/R) machine sequence and minimizing its travel time. In the paper, we study a new bi-objective S/R machine sequencing problem with task release time and due date in a two-depot AS/RS. The objective is to minimize the total travel time of the S/R machine and the total tardiness simultaneously. For the problem, a new bi-objective mixed integer linear programming model is established. Based on problem property analysis, an exact ϵ -constraint method, a non-dominated sorting genetic algorithm II and a promising heuristic are devised for the problem. Especially, the computational results show the efficiency and effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

High utilization of quay cranes is a major objective pursued by seaport terminal managers. Double-cycling technique has been shown to be effective in practice. Complicated with reshuffle operations, the productivity of quay cranes could be further improved, but the problem complexity increases as a side-effect. This paper studies a double-cycling quay crane scheduling problem in which reshuffle containers can be handled internally on the vessel. For this problem, no exact algorithm exists in the literature. We present a dynamic programming approach to optimally solve the problem. Our algorithm runs in polynomial time when the number of container stacks is fixed. We also extend our proposed optimal algorithm to the general case where hatch covers are involved. [ABSTRACT FROM AUTHOR]

Given the scheduling model of bike-sharing, we consider the problem of hitting a set of n axis-parallel line segments in R 2 by a square or an ℓ ∞ -circle (and two squares, or two ℓ ∞ -circles) whose center(s) must lie on some line segment(s) such that the (maximum) edge length of the square(s) is minimized. Under a different tree model, we consider (virtual) hitting circles whose centers must lie on some tree edges with similar minmax-objectives (with the distance between a center to a target segment being the shortest path length between them). To be more specific, we consider the cases when one needs to compute one (and two) centers on some edge(s) of a tree with m edges, where n target segments must be hit, and the objective is to minimize the maximum path length from the target segments to the nearer center(s). We give three linear-time algorithms and an O (n 2 log n) algorithm for the four problems in consideration. [ABSTRACT FROM AUTHOR]

This paper studies a new version of the location problem called the mixedcenterlocation problem. Let P be a set of n points in the plane. We first consider the mixed 2-center problem, where one of the centers must be in P, and we solve it in O(n2logn) time. Second, we consider the mixed k-center problem, where m of the centers are in P, and we solve it in O(nm+O(k-m)) time. Motivated by two practical constraints, we propose two variations of the problem. Third, we present a 2-approximation algorithm and three heuristics solving the mixed k-center problem (k>2). [ABSTRACT FROM AUTHOR]

Price fluctuation is a common phenomenon in the leasing industry. This paper studies the online leasing problem in which the lessee does not know how long he will use the required equipment. Besides, the price of the equipment varies over time, and cannot be learned in advance. We bound the price fluctuations by the definition of the consumer price index. That is, the ratio of the prices between any two consecutive times lies in a predetermined range. By assuming, the lessee has two options for acquiring the equipment: purchase or lease. The problem requires that the leasing strategy should be determined under uncertainties in the using period and the price fluctuations, such that the cost for using the equipment is minimized. We present an optimal online strategy for solving this problem. Computational experiments are conducted to evaluate the characteristics of the problem and the performance of the proposed strategy. [ABSTRACT FROM AUTHOR]

This paper studies an online over-list model of the integrated allocation of berths and quay cranes (QCs) in container terminals with 1-lookahead ability. The objective is to minimize the maximum completion time of container vessels, i.e., the makespan. We focus on two different types of vessels, three berths and a small number of QCs in the hybrid berth layout, with 1-lookahead ability. We propose a (1+2)/2-competitive algorithm for the case with four cranes, a 5/4-competitive algorithm for the case with five cranes and a 4/3-competitive algorithm for the case with six cranes, respectively. All of the algorithms are proved to be optimal. [ABSTRACT FROM AUTHOR]

This paper examines the problem of combining a set of ordinal rankings to form an acceptable consensus ranking. The objective of traditional group decision making problem is to determine the Minimum Violation Ranking. Motived by the applications of adjusted consensus in recent years, we study this problem from a new perspective, for obtaining an acceptable consensus ranking for group decision making. In this paper, every voter ranks a set of alternatives respectively, and we know the acceptability index, which represents the minimum adjustments that are allowed for each voter. The problem is to find the Minimum Acceptable Violation Ranking (MAVR) which minimizes the sum of voter’s unacceptable violations. Besides, we develop a branch and bound ranking algorithm to solve this problem. The suggested improvement include: (1) analysing the ranking preference by two ways: pairwise preference and ranking-based preference; (2) constructing the lower bound and upper bound, which exclude at most half of the feasible solutions in each iteration process. Furthermore, the effectiveness and efficiency of this algorithm are verified with an example and numerical experiments. Finally, we discuss two extensions of the basic MAVR problem: the Minimum Weighted Acceptable Violation problem, whose voters are accompanied with a set of weights or multiples, and the Minimum Hierarchy Acceptable Violation problem, which uses hierarchical acceptability indexes. In addition, our results can be applied to other ranking and subset selection problems in which provide consensus rankings over the alternatives. [ABSTRACT FROM AUTHOR]

Given a graph G=(V,E,D,W), the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex i∈D is either on the tour or within a predetermined distance L to an arbitrary vertex j∈W on the tour, where D⊂V,W⊂V. In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound 11+(k+2)Lk+1 and a CoverTreeTraversal algorithm for online CSP which is proved to be k+α-competitive, where α=0.5+(4k+2)LOPT+2γρ, γ is the approximation ratio for Steiner tree problem and ρ is the maximal number of locations that a customer can be served. When LOPT→0, our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived. [ABSTRACT FROM AUTHOR]

In many fault detection problems, we want to identify all defective items from a set of n items using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. In practice, the number d of defective items is often unknown in advance. In this paper, we propose a randomized group testing procedure RGT for the scenario where the number d of defectives is unknown in advance, and prove that RGT is competitive. By incorporating numerical results, we obtain improved upper bounds on the expected number of tests performed by RGT, for 1≤d≤106. In particular, for 1≤d≤106 and the special case where n is a power of 2, we obtain an upper bound of dlognd+Cd+O(logd) with C≈2.67 on the expected number of tests performed by RGT, which is better than the currently best upper bound in Cheng et al. (INFORMS J Comput 26(4):677-689, 2014). We conjecture that the above improved upper bounds based on numerical results from 1≤d≤106 actually hold for all d≥1. [ABSTRACT FROM AUTHOR]

In the present study, a new strain, Bacillus cereus ZY12, producing phospholipase D (PLD) was identified. The expression of PLD in this strain was found to be induced by its substrate, phosphatidylcholine (PC), and completely silenced by other carbon sources, such as glucose, fructose, and maltose, which are generally used in microbial growth cultures, thus presenting a unique expression pattern different from other PLD-producing microorganisms. This study is the first to report on the ability of B. cereus to produce PLD, and successfully clone its PLD-coding gene and identify its function, extending the knowledge on PLD distribution and evolution in microorganisms. [ABSTRACT FROM AUTHOR]

Based on the well-known longest increasing subsequence problem and longest common increasing subsequence (LCIS) problem, we propose the longest commonly positioned increasing subsequences (LCPIS) problem. Let A=⟨a1,a2,…,an⟩ and B=b1,b2,…,bn be two input sequences. Let Asub=ai1,ai2,…,ail be a subsequence of A and Bsub=bj1,bj2,…,bjl be a subsequence of B such that aik≤aik+1,bjk≤bjk+1(1≤k, and aik and bjk (1≤k≤l) are commonly positioned (have the same index ik=jk) in A and B respectively but these two elements do not need to be equal. The LCPIS problem aims at finding a pair of subsequences Asub and Bsub as long as possible. When all the elements of the two input sequences are positive integers, this paper presents an algorithm with O(nlognloglogM) time to compute the LCPIS, where M=min{max1≤i≤nai,max1≤j≤nbj}. And we also show a dual relationship between the LCPIS problem and the LCIS problem. [ABSTRACT FROM AUTHOR]

In this work we investigate the online over-list MapReduce processing problem on two identical parallel machines, aiming at minimizing the makespan. Jobs are revealed one by one, and each job consists of one map task and one reduce task. The map task can be arbitrarily split and processed on both machines simultaneously, while the reduce task has to be processed on a single machine and it cannot be started unless the map task has been completed. We first show that the general case of the problem reduces to the classical two machine online scheduling model with an optimal competitive ratio of 3/2. For a special case where the map task is at least as long as the reduce task, we prove that no online algorithm can be less than 4/3-competitive. An optimal Greedy algorithm with a matching competitive ratio is proposed as well. [ABSTRACT FROM AUTHOR]

This study considers an evacuation problem where the evacuees try to escape to the boundary of an affected area, which is convex, and a grid network is embedded in the area. The boundary is unknown to the evacuees and we propose an online evacuation strategy based on the Fibonacci sequence. This strategy is proved to have a competitive ratio of 19.5, which is better than the best previously reported result of 21. [ABSTRACT FROM AUTHOR]

MapReduce system is a popular big data processing framework, and the performance of it is closely related to the efficiency of the centralized scheduler. In practice, the centralized scheduler often has little information in advance, which means each job may be known only after being released. In this paper, hence, we consider the online MapReduce scheduling problem of minimizing the makespan, where jobs are released over time. Both preemptive and non-preemptive version of the problem are considered. In addition, we assume that reduce tasks cannot be parallelized because they are often complex and hard to be decomposed. For the non-preemptive version, we prove the lower bound is $$\frac{m+m(\Psi (m)-\Psi (k))}{k+m(\Psi (m)-\Psi (k))}$$ , higher than the basic online machine scheduling problem, where k is the root of the equation $$k=\big \lfloor {\frac{m-k}{1+\Psi (m)-\Psi (k)}+1 }\big \rfloor $$ and m is the quantity of machines. Then we devise an $$(2-\frac{1}{m})$$ -competitive online algorithm called MF-LPT (Map First-Longest Processing Time) based on the LPT. For the preemptive version, we present a 1-competitive algorithm for two machines. [ABSTRACT FROM AUTHOR]

In the MapReduce processing, since map tasks output key-value pairs, and reduce tasks take the pairs output by the map tasks and compute the final results. Therefore, reduce tasks are unknown until their map tasks are finished. Also, we assume that map tasks are preemptive and parallelizable, but reduce tasks are non-parallelizable. With these assumptions, we study the scheduling of minimizing makespan. Both preemptive and non-preemptive reduce tasks are considered. We prove that no matter if preemption is allowed or not, any algorithm has a competitive ratio at least $$2-\frac{1}{h}$$ , we then give two optimal algorithms for these two versions. [ABSTRACT FROM AUTHOR]

We investigate a scheduling problem with job delivery coordination in which the machine has a maintenance time interval. The goal is to minimize the makespan. In the problem, each job needs to be processed on the machine non-preemptively for a certain time, and then transported to a distribution center, by one vehicle with a limited physical capacity. We present a 2-approximation algorithm for the problem, and show that the performance ratio is tight. [ABSTRACT FROM AUTHOR]

We study an integrated production-distribution scheduling problem where jobs are released by customers to a manufacturer over time. The jobs are released online, that is, at any time the information of the number, release and processing times of future jobs is unknown, and the processing time of a job becomes known when the job is released. The manufacturer processes the jobs on a single machine. During the processing of jobs preemption is not allowed. Completed jobs are delivered in batches to customers via sufficient capacitated vehicles. For the objective of minimizing the sum of the total delivery time and the total distribution cost, we present a 3-competitive algorithm for the single-customer case and then extend the result to the multi-customer case. A lower bound of two on the competitive ratio of the problem is also given. [ABSTRACT FROM AUTHOR]

This paper considers the minimax regret vertex 2-sink location problem in a dynamic path network with positive edge lengths and uniform edge capacity. Let $$P$$ be an undirected path graph of $$n$$ vertices, and the weight (initial supply) of every vertex is known as an interval. The problem is to find two vertices $$x$$ and $$y$$ as two sinks on the path such that all the weights can evacuate to $$x$$ and $$y$$ with minimum regret of evacuation time in case of an emergency for any possible weight distribution. We present an $$O(n^3\log n)$$ time algorithm. [ABSTRACT FROM AUTHOR]

Recently, Liu et al. (J Combin Optim 21:138-149, ) studied the semi-online scheduling problem on two machines under a grade of service provision. As the sum of jobs' processing times $$\varSigma $$ is known in advance and the processing times are bounded by an interval $$[1,\alpha ]$$ where $$1< \alpha <2$$ , they presented an algorithm which is $$\frac{1+\alpha }{2}$$ -competitive when $$\varSigma \ge \frac{2\alpha }{\alpha -1}$$ . In this paper, we give a modified algorithm which is shown to be optimal for arbitrary $$\alpha $$ and $$\varSigma $$ . [ABSTRACT FROM AUTHOR]

Disasters often bring great uncertainty to the urban traffic network. Considering a special urban network and the rescuers' communication, this paper focuses on the real-time rescue routing problem from a source node to an emergency spot. There are some uncertain edge blockages, which cannot be observed in advance. Our goal is to make all the rescuers arrive at the emergency spot as quickly as possible. We study the problem in two scenarios: (1) without communication $$(S_1)$$ , the rescuers can not communicate with the others; (2) with complete communication $$(S_2)$$ , the rescuers can share their information about the tracks and the detected edge blockages instantaneously. These two scenarios are both analyzed on the grid network and the general network, respectively. The results of worst case analysis indicate that the consideration of both the grid network and the rescuers' communication can significantly improve the rescue efficiency. [ABSTRACT FROM AUTHOR]

This paper studies an incremental version of the k-center problem with centers constrained to lie on boundary of a convex polygon. In the incremental k-center problem we considered, we are given a set of n demand points inside a convex polygon, facilities are constrained to lie on its boundary. Our algorithm produces an incremental sequence of facility sets $$B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B_{n}$$ , where each $$B_{k}$$ contains k facilities. Such an algorithm is called $$\alpha $$ -competitive, if for any k, the maximum of the ratio between the value of solution $$B_{k}$$ and the value of an optimal k-center solution is no more than $$\alpha $$ . We present a polynomial time incremental algorithm with a competitive ratio $$\frac{3\sqrt{3}}{2}$$ and we also prove a lower bound of 2. [ABSTRACT FROM AUTHOR]

Considering the customer psychology while waiting to be served, we introduce a more reasonable form of deadlines into online traveling salesman problem (OL-TSP) with service flexibility. The salesman can choose whether to serve or not when a new request arrives. By rejecting the request or missing its deadline, penalties will be generated. The goal is to minimize server's costs (travel makespan plus the penalties of missed requests). We show that no deterministic or randomized online algorithms can achieve constant competitive ratio for OL-TSP with deadlines and service flexibility on general metric space. While on constrained metric space (such as truncated line segment), we present lower bound, give an algorithm, and analyze the competitive ratio. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the consistency issues of interval pairwise comparison matrices in detail. Using logarithmic Manhattan distance to define the deviation degree of a pairwise comparison matrix to consistent pairwise comparison matrices, we propose a new consistency index of pairwise comparison matrices. Based on this consistency index of pairwise comparison matrices, we develop a consistency index of interval pairwise comparison matrices. Several desired properties of the proposed consistency indexes are presented. Furthermore, linear programming (LP) models are developed to compute the consistency indexes. Then, we propose a LP-based consistency improving model, which optimally preserves original pairwise comparison information in improving consistency. Meanwhile, considering the uncertainty plays an important role in the consistency index of interval pairwise comparison matrices, this consistency improving model is extended to simultaneously manage the uncertain degree in interval pairwise comparison matrices. Finally, we discuss the consistency-based prioritization method, and propose the strong consistency index of interval pairwise comparison matrices. [ABSTRACT FROM AUTHOR]

This paper studies the online $$k$$ -server problem with max-distance objective, i.e. minimizing the maximum distance moved among all the servers. For this objective, we prove that no deterministic online algorithm has a competitive ratio better than $$k$$ . We also analyze several classical algorithms for two special cases and show that some algorithms do have a competitive ratio of $$k$$ and hence optimal. Consequently, we conjecture that any metric space allows for a deterministic $$k$$ -competitive $$k$$ -server algorithm with max-distance objective. [ABSTRACT FROM AUTHOR]

This paper proposes the optimal shortest path set problem in an undirected graph $$G=(V,E)$$ , in which some vehicles have to go from a source node $$s$$ to a destination node $$t$$ . However, at most $$k$$ edges in the graph may be blocked during the traveling. The goal is to find a minimum collection of paths for the vehicles before they start off to assure the fastest arrival of at least one vehicle, no matter which $$l$$ $$(0\le l\le k)$$ edges are blocked. We consider two scenarios for this problem. In the first scenario with $$k=1$$ , we propose the concept of common replacement path and design the Least-Overlap Algorithm to find the common replacement path. Based on this, an algorithm to compute the optimal shortest path set is presented and its time complexity is proved to be $$O(n^2)$$ . In the second scenario with $$k>1$$ , we consider the case where the blocked edges are consecutive ones on a shortest path from $$s$$ to $$t$$ and the vertices connecting two blocked edges are also blocked (i.e., routes passing through these vertices are not allowed), and an algorithm is presented to compute the optimal shortest path set in this scenario with time complexity $$O(mn+k^2n^2\log n)$$ . [ABSTRACT FROM AUTHOR]