Journal of Combinatorial Optimization
Journal Prestige (SJR): 0.579 Citation Impact (citeScore): 1 Number of Followers: 7 Hybrid journal (It can contain Open Access articles) ISSN (Print) 15732886  ISSN (Online) 13826905 Published by SpringerVerlag [2469 journals] 
 Computing a consensus trajectory in a vehicular network

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 NPhard and we present a simple factor2 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 NPhard 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 NPhard. We implement a simple greedy algorithm and a variation of the 1.5approximation 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: 20220924

 Fast algorithms for supermodular and nonsupermodular minimization via
bicriteria strategy
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we concentrate on exploring fast algorithms for the minimization of a nonincreasing supermodular or nonsupermodular function f subject to a cardinality constraint. As for the nonsupermodular 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 bicriteria 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 Cmeans problems are studied at the end.
PubDate: 20220922

 Online scheduling with migration on two hierarchical machines

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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: 20220915

 Bounding quality of pure Nash equilibria in dualrole facility location
games
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study a dualrole 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 polynomialtime algorithm, then use the price of anarchy (PoA) to measure the quality of PNE under social objectives of minimizing the maximum/social cost. For dualrole 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 LLipschitz 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 \{L1,0\}\right] \) .
PubDate: 20220913

 Capacitance pin defect detection based on deep learning

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Mask RCNN network based on deep learning algorithm is specifically optimized for the small visual defects of gears. After comparison, the ResNet101 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 RCNN network can achieve a defect detection rate that is above 98%.
PubDate: 20220909

 Linear time algorithms on mirror trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 SumCut cost criterion for which a linear time algorithm is exhibited.
PubDate: 20220909

 A columngenerationbased approach for an integrated service planning and
physician scheduling problem considering reconsultation
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, an integrated service planning and physician scheduling problem in the outpatient department is investigated, considering the reconsultation 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., CGVNS, is developed to solve the problem. In the computational experiments, the proposed CGVNS is compared with the original model in the smallscale instances. In the largescale instances, the proposed CGVNS is compared with CGGurobi, which applies the hybrid CG and the solver Gurobi to calculate the restricted MP and the PPs. The performances of the proposed CGVNS and the CGGurobi approach are further tested in the experiments.
PubDate: 20220907

 Algorithms for maximum internal spanning tree problem for some graph
classes
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 NPhard, even for bipartite and chordal graphs, two important subclasses of graphs, the MIST problem also remains NPhard for these graph classes. In this paper, we propose lineartime 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: 20220905

 Exponentialtime algorithms for parallel machine scheduling problems

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 InclusionExclusion, it solves multiple relaxed singlemachine 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 worstcase complexity bounds. While not the fastest in practice compared to specialized algorithms, this generic algorithm enhances the stateoftheart theoretical worstcase complexity bounds of several particular parallel machine scheduling problems.
PubDate: 20220903

 Online algorithms for the maximum kinterval coverage problem

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study the online maximum coverage problem on a target interval, in which, given an online sequence of subintervals (which may intersect among each other) to arrive, we aim to select at most k of the subintervals such that the total covered length of the target interval is maximized. The decision to accept or reject each subinterval is made immediately and irrevocably right at the release time of the subinterval. We comprehensively study various settings of this problem regarding both the length of each released subinterval and the total number of released subintervals. To begin with, we investigate the offline version of the problem where the sequence of all the released subintervals is known in advance to the decisionmaker and propose two polynomialtime optimal solutions to different settings of our offline problem. For the online problem, lower bounds on the competitive ratio are first proposed on our welldesigned release schemes of subintervals. Then, we propose a SinglethreshOldbased deterministic Algorithm (SOA), which adds a subinterval if the added length without overlap exceeds a certain threshold, achieving competitive ratios close to the lower bounds. Further, we extend SOA to a DoublethreshOldsbased 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 worstcase scenario. Moreover, we show that more thresholds cannot induce better worstcase performance of an online deterministic algorithm as long as those thresholds are used in nonincreasing order in accepting subintervals.
PubDate: 20220903

 Online data caching in edgecloud collaborative system with the data
center
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 edgecloud 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: 20220902

 Competitive analysis of online machine rental and online parallel machine
scheduling problems with workload fence
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract 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.
PubDate: 20220901

 The minp robust optimization approach for facility location problem under
uncertainty
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Improper value of the parameter p in robust constraints will result in no feasible solutions while applying stochastic probustness optimization approach (pSRO) to solving facility location problems under uncertainty. Aiming at finding the lowest critical pvalue of parameter p and corresponding robust optimal solution, we developed a novel robust optimization approach named as minp robust optimization approach (minpRO) for Pmedian problem (PMP) and fixed cost Pmedian problem (FPMP). Combined with the nearest allocation strategy, the vertex substitution heuristic algorithm is improved and the influencing factors of the lowest critical pvalue 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 pvalue with given number of new facilities. However, the number of new facilities has a different impact on lowest critical pvalue with the given fluctuation range of data. As the number of new facilities increases, the lowest critical pvalue for PMP and FPMP increases and decreases, respectively.
PubDate: 20220901

 The upper bounds on the Steiner kWiener index in terms of minimum and
maximum degrees
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract For \(k \in {\mathbb {N}},\) Ali et al. (Discrete Appl Math 160:18451850, 2012) introduce the Steiner kWiener 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 kdistance \(\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 trianglefree or a \(C_{4}\) free graph.
PubDate: 20220901

 A siftingedges algorithm for accelerating the computation of absolute
1center in graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Let \(G = (V, E, w)\) be an undirected connected edgeweighted graph, where V is the nvertices set, E is the medges set, and \(w: E \rightarrow \mathbb {R}^+\) is a positive edgeweight 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 1Center 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 polynomialtime 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 1center is just a vertex 1center if the allpairs 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 wellknown 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: 20220901

 Paired domination versus domination and packing number in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 kpacking 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 kpacking number is the order of a largest kpacking 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 NPhard 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 polynomialtime recognition algorithm. We also prove that even for a bipartite graph, it is NPhard to determine whether \(\gamma _{pr}(G)=\gamma _{t}(G)\) . We finally prove that it is both NPhard to determine whether \(\gamma _{pr}(G)=2\rho _{4}(G)\) and whether \(\gamma _{pr}(G)=2\rho _{3}(G)\) .
PubDate: 20220901

 An efficient approach for searching optimal multikeywords coverage routes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Keywordaware optimal route queries are a combinatorial optimization problem with three factors, namely keyword coverage, route budget constraint and route popularity, which is NPhard. 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 Keywordaware 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: 20220901

 Sharp upper bound of injective coloring of planar graphs with girth at
least 5
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract An injective kcoloring of a graph G is a kcoloring 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 kcoloring. 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: 20220901

 Particle swarm optimization basedalgorithms to solve the twomachine
crossdocking flow shop problem: just in time scheduling
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Crossdocking 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 twomachine crossdocking scheduling problem within a JustInTime (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 NPhard 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: 20220901

 Jobshop schedulingjoint consideration of production, transport, and
storage/retrieval systems
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 mixedinteger linear programming (MILP) model that can be solved to optimality for smallsized instances. We also propose a hybrid simulated annealing (HSA) algorithm to find good quality solutions for larger instances. The HSA incorporates a late acceptance hillclimbing 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 smallsized instances as well as the effectiveness, efficiency, and robustness of the HSA on medium and largesized 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: 20220901
