Subjects -> STATISTICS (Total: 130 journals)
 The end of the list has been reached or no journals were found for your choice.
Similar Journals
 Journal of Combinatorial OptimizationJournal Prestige (SJR): 0.579 Citation Impact (citeScore): 1Number of Followers: 7      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1573-2886 - ISSN (Online) 1382-6905 Published by Springer-Verlag  [2469 journals]
• Computing a consensus trajectory in a vehicular network

Abstract: Abstract In this paper, we study the problem of computing a consensus trajectory of a vehicle given the history of Points of Interest visited by the vehicle over a certain period of time. The problem arises when a system tries to establish the social connection between two vehicles in a vehicular network, where three versions of the problem are studied. Formally, given a set of m trajectories, the first version of the problem is to compute a target (median) sequence T over $$\varSigma$$ such that the sum of similarity measure (i.e., number of adjacencies) between T and all $$S_i$$ ’s is maximized. For this version, we show that the problem is NP-hard and we present a simple factor-2 approximation based on a greedy method. We implement the greedy algorithm and a variation of it which is based on a more natural greedy search on a new data structure called adjacency map. In the second version of the problem where the sequence T is restricted to be a permutation, we show that the problem remains NP-hard but the approximation factor can be improved to 1.5. In the third version where the sequence T has to contain all letters of $$\varSigma$$ , we again prove that it is NP-hard. We implement a simple greedy algorithm and a variation of the 1.5-approximation algorithm for the second version, and which are used to construct solution for the third version. Our algorithms are tested on the simulation data and the empirical results are very promising.
PubDate: 2022-09-24

• Fast algorithms for supermodular and non-supermodular minimization via
bi-criteria strategy

Abstract: Abstract In this paper, we concentrate on exploring fast algorithms for the minimization of a non-increasing supermodular or non-supermodular function f subject to a cardinality constraint. As for the non-supermodular minimization problem with the weak supermodularity ratio r, we can obtain a $$(1+\epsilon )$$ -approximation algorithm with adaptivity $$O(\frac{n}{\epsilon }\log {\frac{r n \cdot f(\emptyset )}{\epsilon \cdot \mathtt {OPT}}})$$ under the bi-criteria strategy, where $$\mathtt {OPT}$$ denotes the optimal objective value of the problem. That is, instead of selecting at most k elements on behalf of the constraint, the cardinality of the output may reach to $$\frac{k}{ r}\log {\frac{f(\emptyset )}{\epsilon \cdot \mathtt {OPT}}}$$ . Moreover, for the supermodular minimization problem, we propose two $$(1+\epsilon )$$ -approximation algorithms for which the output solution X is of size $$X_0 + O\left( k \log {\frac{f(X_0)}{\epsilon \cdot \mathtt {OPT}}}\right)$$ . The adaptivities of this two algorithms are $$O \left( \log ^2n \cdot \log \frac{f(X_0)}{\epsilon \cdot \mathtt {OPT}}\right)$$ and $$O\left( \log n \cdot \log \frac{f(X_0)}{\epsilon \cdot \mathtt {OPT}}\right)$$ , where $$X_0$$ is an input set and $$\mathtt {OPT}$$ is the optimal value. Applications to group sparse linear regression problems and fuzzy C-means problems are studied at the end.
PubDate: 2022-09-22

• Online scheduling with migration on two hierarchical machines

Abstract: Abstract We consider online scheduling with migration on two hierarchical machines, with the goal of minimizing the makespan. In this model, one of the machines can run any job, while the other machine can only receive jobs from a subset of the input jobs. In addition, in this problem, there is a constant parameter $$M \ge 0$$ , called the migration factor. Jobs are presented one by one, and every arrival of a new job of size x does not only require the algorithm to assign the job to one of the machines, but it also allows the algorithm to reassign any subset of previously presented jobs, whose total size is at most $$M \cdot x$$ . We show that no algorithm with a finite migration factor has a competitive ratio below $$\frac{3}{2}$$ , and design an algorithm with this competitive ratio and migration factor 1. We prove that this is the best possible result, in the sense that no algorithm with a smaller migration factor can have a competitive ratio of $$\frac{3}{2}$$ . This provides tight bounds on the competitive ratio for all values $$M\ge 1$$ . We also find tight bounds on the competitive ratio for many other values of M.
PubDate: 2022-09-15

• Bounding quality of pure Nash equilibria in dual-role facility location
games

Abstract: Abstract We study a dual-role game setting of locating facilities in a metric space where each agent can open a facility at her location or be a customer to receive the service, and an opening cost function is given to represent the cost of opening a facility at some specific location. We first show the existence of pure Nash equilibria (PNE) in such games by a polynomial-time algorithm, then use the price of anarchy (PoA) to measure the quality of PNE under social objectives of minimizing the maximum/social cost. For dual-role facility location games with general opening cost functions, we show the PoA under maximum/social cost can tend to be infinite. However, for games with L-Lipschitz conditioned opening cost functions where $$L\ge 0$$ is a given parameter, the PoA under maximum cost is exactly $$L+1$$ and the PoA under social cost is bounded by the interval $$\left[ (n+L)/3, n+\max \{L-1,0\}\right]$$ .
PubDate: 2022-09-13

• Capacitance pin defect detection based on deep learning

Abstract: Abstract Mask R-CNN network based on deep learning algorithm is specifically optimized for the small visual defects of gears. After comparison, the ResNet-101 residual neural network is used as the image sharing feature for network extraction. Subsequently, the unreasonable convolution of the feature extraction process $${P}_{5}$$ in the characteristic pyramid network is removed to improve the defect detection rate indicator. Finally, the sizes of the anchor and label frames are adjusted according to the dimensioning of the tiny objects in the capacitance sample, and an appropriate aspect ratio is set to achieve the effective training of the network in the candidate area. Experiments show that the optimized Mask R-CNN network can achieve a defect detection rate that is above 98%.
PubDate: 2022-09-09

• Linear time algorithms on mirror trees

Abstract: Abstract We address in this paper two problems on mirror graphs. The first is the recognition problem. While it is graph isomorphism complete, we show the analogous problem of recognizing mirror trees is solvable in linear time. The second problem we are tackling in this study is the linear ordering problem on mirror trees with respect to Directed Sum-Cut cost criterion for which a linear time algorithm is exhibited.
PubDate: 2022-09-09

• A column-generation-based approach for an integrated service planning and
physician scheduling problem considering re-consultation

Abstract: Abstract In this paper, an integrated service planning and physician scheduling problem in the outpatient department is investigated, considering the re-consultation of patients as well as multiple types of physicians and consultation services. The problem is to determine 1) the number of patients to be served for each type of consultation service in each shift of a planning horizon and, 2) the working schedule for all planned physicians during the horizon, to maximize the total net benefit of the department. An integer programming model is presented as the original model, which is further decomposed into a Master Problem (MP) and several Pricing Problems (PPs). An approach that incorporates the Column Generation (CG) heuristic and the Variable Neighborhood Search algorithm (VNS), i.e., CG-VNS, is developed to solve the problem. In the computational experiments, the proposed CG-VNS is compared with the original model in the small-scale instances. In the large-scale instances, the proposed CG-VNS is compared with CG-Gurobi, which applies the hybrid CG and the solver Gurobi to calculate the restricted MP and the PPs. The performances of the proposed CG-VNS and the CG-Gurobi approach are further tested in the experiments.
PubDate: 2022-09-07

• Algorithms for maximum internal spanning tree problem for some graph
classes

Abstract: Abstract For a given graph G, a maximum internal spanning tree of G is a spanning tree of G with maximum number of internal vertices. The Maximum Internal Spanning Tree (MIST) problem is to find a maximum internal spanning tree of the given graph. The MIST problem is a generalization of the Hamiltonian path problem. Since the Hamiltonian path problem is NP-hard, even for bipartite and chordal graphs, two important subclasses of graphs, the MIST problem also remains NP-hard for these graph classes. In this paper, we propose linear-time algorithms to compute a maximum internal spanning tree of cographs, block graphs, cactus graphs, chain graphs and bipartite permutation graphs. The optimal path cover problem, which asks to find a path cover of the given graph with maximum number of edges, is also a well studied problem. In this paper, we also study the relationship between the number of internal vertices in maximum internal spanning tree and number of edges in optimal path cover for the special graph classes mentioned above.
PubDate: 2022-09-05

• Exponential-time algorithms for parallel machine scheduling problems

Abstract: Abstract In this paper we consider the problem of scheduling a set of jobs on unrelated parallel machines in the presence of job release dates and deadlines, and we deal with the minimization of any general regular, either maximum or sum, objective function. We describe a generic exact exponential algorithm, solving a problem in two phases. In the first phase, given a threshold objective value, the algorithm counts the number of schedules whose objective value is at most the threshold. For this purpose, by using Inclusion-Exclusion, it solves multiple relaxed single-machine problems by means of dynamic programming. In the second phase, the algorithm uses this counting procedure to determine the optimal objective value and build, step by step, an explicit optimal schedule. The strength of this algorithm is to manage a wide class of parallel machine scheduling problems, and to achieve, on a theoretical point on view, moderate exponential time and pseudopolynomial space worst-case complexity bounds. While not the fastest in practice compared to specialized algorithms, this generic algorithm enhances the state-of-the-art theoretical worst-case complexity bounds of several particular parallel machine scheduling problems.
PubDate: 2022-09-03

• Online algorithms for the maximum k-interval coverage problem

Abstract: Abstract We study the online maximum coverage problem on a target interval, in which, given an online sequence of sub-intervals (which may intersect among each other) to arrive, we aim to select at most k of the sub-intervals such that the total covered length of the target interval is maximized. The decision to accept or reject each sub-interval is made immediately and irrevocably right at the release time of the sub-interval. We comprehensively study various settings of this problem regarding both the length of each released sub-interval and the total number of released sub-intervals. To begin with, we investigate the offline version of the problem where the sequence of all the released sub-intervals is known in advance to the decision-maker and propose two polynomial-time optimal solutions to different settings of our offline problem. For the online problem, lower bounds on the competitive ratio are first proposed on our well-designed release schemes of sub-intervals. Then, we propose a Single-threshOld-based deterministic Algorithm (SOA), which adds a sub-interval if the added length without overlap exceeds a certain threshold, achieving competitive ratios close to the lower bounds. Further, we extend SOA to a Double-threshOlds-based deterministic Algorithm (DOA) by using the first threshold for exploration and the second threshold (larger than the first one) for exploitation. With the two thresholds generated by our proposed program, we show that DOA outperforms SOA slightly in the worst-case scenario. Moreover, we show that more thresholds cannot induce better worst-case performance of an online deterministic algorithm as long as those thresholds are used in non-increasing order in accepting sub-intervals.
PubDate: 2022-09-03

• Online data caching in edge-cloud collaborative system with the data
center

Abstract: Abstract In edge computing, the edge node can provide certain accessible storage and computing resources for the surrounding users. Caching data on the edge node can quickly retrieve the required data and complete the user’s requests with low delay. However, the resources of edge servers are limited and sometimes have to gain the data by transfering from other servers or buying from data centers at the cloud. Traditionally, data center is just regard as a place of purchasing data, and the data is always available for the buyer after purchase. However, we believe that these data have a validity period. After the buyer purchases the data, it only provides limited calls for free. Based on this assumption, in this paper, we study the data caching problem in the edge-cloud collaborative system to minimize the total cost. Without knowing the information of users’ future request flow, we propose an online algorithm. What’s more, the asymptotic competition ratio of the algorithm in the worst case is 3.
PubDate: 2022-09-02

• Competitive analysis of online machine rental and online parallel machine

PubDate: 2022-09-01

• The min-p robust optimization approach for facility location problem under
uncertainty

Abstract: Abstract Improper value of the parameter p in robust constraints will result in no feasible solutions while applying stochastic p-robustness optimization approach (p-SRO) to solving facility location problems under uncertainty. Aiming at finding the lowest critical p-value of parameter p and corresponding robust optimal solution, we developed a novel robust optimization approach named as min-p robust optimization approach (min-pRO) for P-median problem (PMP) and fixed cost P-median problem (FPMP). Combined with the nearest allocation strategy, the vertex substitution heuristic algorithm is improved and the influencing factors of the lowest critical p-value are analyzed. The effectiveness and performance of the proposed approach are verified by numerical examples. The results show that the fluctuation range of data is positively correlated with the lowest critical p-value with given number of new facilities. However, the number of new facilities has a different impact on lowest critical p-value with the given fluctuation range of data. As the number of new facilities increases, the lowest critical p-value for PMP and FPMP increases and decreases, respectively.
PubDate: 2022-09-01

• The upper bounds on the Steiner k-Wiener index in terms of minimum and
maximum degrees

Abstract: Abstract For $$k \in {\mathbb {N}},$$ Ali et al. (Discrete Appl Math 160:1845-1850, 2012) introduce the Steiner k-Wiener index $$SW_{k}(G)=\sum _{S\in V(G)} d(S),$$ where d(S) is the minimum size of a connected subgraph of G containing the vertices of S. The average Steiner k-distance $$\mu _{k}(G)$$ of G is defined as $$\genfrac(){0.0pt}1{n}{k}^{-1} SW_{k}(G)$$ . In this paper, we give some upper bounds on $$SW_{k}(G)$$ and $$\mu _{k}(G)$$ in terms of minimum degree, maximum degree and girth in a triangle-free or a $$C_{4}$$ -free graph.
PubDate: 2022-09-01

• A sifting-edges algorithm for accelerating the computation of absolute
1-center in graphs

Abstract: Abstract Let $$G = (V, E, w)$$ be an undirected connected edge-weighted graph, where V is the n-vertices set, E is the m-edges set, and $$w: E \rightarrow \mathbb {R}^+$$ is a positive edge-weight function. Given $$G = (V, E, w)$$ , a subset $$X \subseteq V$$ of p terminals, and a subset $$F \subseteq E$$ of candidate edges, the Absolute 1-Center Problem (A1CP) aims to find a point on some edge in F to minimize the distance from it to X. This paper revisits this classic and polynomial-time solvable problem from a novel perspective and finds some new and nontrivial properties of it, with the highlight of establishing the relationship between the A1CP and the saddle point of distance matrix. In this paper, we prove that an absolute 1-center is just a vertex 1-center if the all-pairs shortest paths distance matrix from the vertices covered by the candidate edges in F to X has a (global) saddle point. Furthermore, we define the local saddle point of edge and demonstrate that we can sift the candidate edge having a local saddle point. By incorporating the method of sifting edges into the framework of the well-known Kariv and Hakimi’s algorithm, we develop an $$O(m + p m^*+ n p \log p)$$ -time algorithm for A1CP, where $$m^*$$ is the number of the remaining candidate edges. Specifically, it takes $$O(m^*n + n^2 \log n)$$ time to apply our algorithm to the classic A1CP when the distance matrix is known and $$O(m n + n^2 \log n)$$ time when the distance matrix is unknown, which are smaller than $$O(mn + n^2 \log n)$$ and $$O(mn + n^3)$$ of Kariv and Hakimi’s algorithm, respectively.
PubDate: 2022-09-01

• Paired domination versus domination and packing number in graphs

Abstract: Abstract Given a graph $$G=(V(G), E(G))$$ , the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by $$\gamma (G)$$ , $$\gamma _{pr}(G)$$ , and $$\gamma _{t}(G)$$ , respectively. For a positive integer k, a k-packing in G is a set $$S \subseteq V(G)$$ such that for every pair of distinct vertices u and v in S, the distance between u and v is at least $$k+1$$ . The k-packing number is the order of a largest k-packing and is denoted by $$\rho _{k}(G)$$ . It is well known that $$\gamma _{pr}(G) \le 2\gamma (G)$$ . In this paper, we prove that it is NP-hard to determine whether $$\gamma _{pr}(G) = 2\gamma (G)$$ even for bipartite graphs. We provide a simple characterization of trees with $$\gamma _{pr}(G) = 2\gamma (G)$$ , implying a polynomial-time recognition algorithm. We also prove that even for a bipartite graph, it is NP-hard to determine whether $$\gamma _{pr}(G)=\gamma _{t}(G)$$ . We finally prove that it is both NP-hard to determine whether $$\gamma _{pr}(G)=2\rho _{4}(G)$$ and whether $$\gamma _{pr}(G)=2\rho _{3}(G)$$ .
PubDate: 2022-09-01

• An efficient approach for searching optimal multi-keywords coverage routes

Abstract: Abstract Keyword-aware optimal route queries are a combinatorial optimization problem with three factors, namely keyword coverage, route budget constraint and route popularity, which is NP-hard. Previous work takes an adjacent edge expansion approach to get an approximate result and the computational complexity is proportional to the number of vertices and edges of the road network, which is not scalable for large road networks or road networks with sparse points of interest. Motivated by this, we propose an algorithm called Keyword-aware Skyline Route Generating (KSRG*). KSRG* consists of a preprocessing stage, in which KSRG* computes all the skyline routes for each pair of vertices, and an expansion stage, in which KSRG* expands feasible routes from the source vertex to target vertex via vertices containing keywords. Based on KSRG*, another two approximation algorithms with performance guarantees, namely KSRG $$^{+}$$ and KSRG $$^{++}$$ are proposed. KSRG $$^{+}$$ applies three acceleration strategies to KSRG* to greatly reduce the routes to be expanded. KSRG $$^{++}$$ combines KSRG $$^{+}$$ with a clustering strategy to solve the inefficient performance when the number of the vertices containing the same query keyword is large. Comprehensive experiments on the datasets of four real road networks show that the execution time and accuracy of results of KSRG $$^+$$ and KSRG $$^{++}$$ outperform the state of the art methods.
PubDate: 2022-09-01

• Sharp upper bound of injective coloring of planar graphs with girth at
least 5

Abstract: Abstract An injective k-coloring of a graph G is a k-coloring c (not necessarily proper) such that $$c(u)\ne c(v)$$ whenever u, v has a common neighbor in G. The injective chromatic number of G, denoted by $$\chi _i(G)$$ , is the least integer k such that G has an injective k-coloring. We prove that the injective chromatic number of planar graphs with $$g \ge 5$$ and $$\Delta \ge 2339$$ is at most $$\Delta + 1$$ , and this bound is sharp.
PubDate: 2022-09-01

• Particle swarm optimization based-algorithms to solve the two-machine
cross-docking flow shop problem: just in time scheduling

Abstract: Abstract Cross-docking is an innovative logistical strategy which provides less inventory holding costs, less transportation costs and fast customer deliveries without storage in between or less than 24 hours. In this paper, we address the two-machine cross-docking scheduling problem within a Just-In-Time (JIT) context. This latter requires the punctuality and exactness of product deliveries. To satisfy this target, we aim to minimize the total earliness and tardiness, then early or tardy deliveries are discouraged. This study presents a great contribution in solving such NP-hard problem while applying different versions of the PSO (Particle Swarm Optimization) algorithm. One of them is hybridized with the Genetic Algorithm (GA). This latter is then shown to be the best one over computational experiments using different sized instances and by determining a percentage deviation from a developed lower bound.
PubDate: 2022-09-01

• Job-shop scheduling-joint consideration of production, transport, and
storage/retrieval systems

Abstract: Abstract This paper proposes a new problem by integrating the job shop scheduling, the part feeding, and the automated storage and retrieval problems. These three problems are intertwined and the performance of each of these problems influences and is influenced by the performance of the other problems. We consider a manufacturing environment composed of a set of machines (production system) connected by a transport system and a storage/retrieval system. Jobs are retrieved from storage and delivered to a load/unload area (LU) by the automated storage retrieval system. Then they are transported to and between the machines where their operations are processed on by the transport system. Once all operations of a job are processed, the job is taken back to the LU and then returned to the storage cell. We propose a mixed-integer linear programming (MILP) model that can be solved to optimality for small-sized instances. We also propose a hybrid simulated annealing (HSA) algorithm to find good quality solutions for larger instances. The HSA incorporates a late acceptance hill-climbing algorithm and a multistart strategy to promote both intensification and exploration while decreasing computational requirements. To compute the optimality gap of the HSA solutions, we derive a very fast lower bounding procedure. Computational experiments are conducted on two sets of instances that we also propose. The computational results show the effectiveness of the MILP on small-sized instances as well as the effectiveness, efficiency, and robustness of the HSA on medium and large-sized instances. Furthermore, the computational experiments clearly shown that importance of optimizing the three problems simultaneous. Finally, the importance and relevance of including the storage/retrieval activities are empirically demonstrated as ignoring them leads to wrong and misleading results.
PubDate: 2022-09-01

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762