Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print 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: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print 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 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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print 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 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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print 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 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
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Given a graph G and a list assignment L(v) for each vertex of v of G, a proper L-list-coloring of G is a function that maps every vertex to a color in L(v) such that no pair of adjacent vertices have the same color. We say that a graph is k-list-colorable when every vertex v has a list of colors of size at least k. A 2-distance coloring is a coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance list ( \(\Delta +2\) )-coloring for planar graphs with girth at least 10 and maximum degree \(\Delta \ge 4\) . PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Given a set of n points and a set of m sensors on the plane, each sensor s can adjust its power p(s) and the covering range which is a disk of radius r(s) satisfying \(p(s)=c\cdot r(s)^{\alpha }\) . The minimum power partial cover problem, introduced by Freund (Proceedings of international workshop on approximation and online algorithms, pp 137–150. 2011. http://citeseerx.ist.psu.edu/viewdoc/summary'doi=10.1.1.737.1320), is to determine the power assignment on every sensor such that at least k ( \(k\le n\) ) points are covered and the total power consumption is minimized. By generalizing the method in Li (Journal of Com. Opti.2020. https://doi.org/10.1007/s10878-020-00567-3) whose approximation ratio is \(3^{\alpha }\) and enlarging the radius of each disk in the relaxed independent set, we present an \(O(\alpha )\) -approximation algorithm. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The fractional matching preclusion number of a graph G, denoted by fmp(G), is the minimum number of edges whose deletion results in a graph with no fractional perfect matchings. Let \(G_{k,n}\) be the complete n-balanced k-partite graph, whose vertex set can be partitioned into k parts, each has n vertices and whose edge set contains all edges between two distinct parts. In this paper, we prove that if \(k=3\) or 5 and \(n=1\) , then \(fmp(G_{k,n})=\delta (G_{k,n})-1\) ; otherwise \(fmp(G_{k,n})=\delta (G_{k,n})\) . PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We study routing and searching decisions of a search-and-detection (SDT) team on a road network under online uncertainty setting. Given an undirected edge-weighted bounded graph, a static target is positioned at an unknown vertex among potential target vertices in the graph. A non-negative search cost is given on each of the potential target vertices. The target is detected once the SDT searches its corresponding vertex. There may be some non-recoverable online blockages in the graph, but the existence of blockages is unknown to the SDT initially. If a blockage exists in the graph, it is disclosed online once the SDT visits one of its end-vertices. The graph stays connected when the blockages are omitted from it. The SDT begins from a certain vertex and aims to identify a route without any blocked edges which detects the target with minimum total traveling and search cost. We analyze this problem from a competitive analysis perspective under two scenarios with and without blockages. For the scenario with blockages, we provide a tight lower bound on the competitive ratio of deterministic solutions, an optimal deterministic solution, a randomized solution with a bounded expected competitive ratio, together with lower and upper bounds on the expected competitive ratio of the optimal randomized solutions. For the scenario without blockages, we provide tight lower bounds as well as optimal deterministic and randomized solutions. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a weight function \(w: N \rightarrow \mathbb {R}_+\) , r monotone submodular functions \(f_1,f_2,\ldots ,f_r\) over N and requirements \(k_1,k_2,\ldots ,k_r\) the goal is to find a minimum weight subset \(S \subseteq N\) such that \(f_i(S) \ge k_i\) for \(1 \le i \le r\) . We refer to this problem as Multi-Submod-Cover and it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR. arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with \(r=1\) Multi-Submod-Cover generalizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced to Submod-SC. A simple greedy algorithm gives an \(O(\log (kr))\) approximation where \(k = \sum _i k_i\) and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm for Multi-Submod-Cover that covers each constraint to within a factor of \((1-1/e-\varepsilon )\) while incurring an approximation of \(O(\frac{1}{\epsilon }\log r)\) in the cost. Second, we consider the special case when each \(f_i\) is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Many real-world optimization problems involve two different subsets of variables: decision variables, and those variables which are not present in the cost function but constrain the solutions, and thus, must be considered during optimization. Thus, dependencies between and within both subsets of variables must be considered. In this paper, an estimation of distribution algorithm (EDA) is implemented to solve this type of complex optimization problems. A Gaussian Bayesian network is used to build an abstraction model of the search space in each iteration to identify patterns among the variables. As the algorithm is initialized from data, we introduce a new hyper-parameter to control the influence of the initial data in the decisions made during the EDA execution. The results show that our algorithm improves the cost function more than the expert knowledge does. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The radius of the outer Dikin ellipsoid of the intersection of m ellipsoids due to Fu et al. (J. Comb. Optim., 2, 29-50, 1998) is corrected from m to \(\sqrt{m^2+m}\) . The approximation bound for the general convex quadratic constrained nonconvex quadratic program is correspondingly corrected. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The residual value of the equipment is an important and inevitable issue for any decision-making process of equipment leasing. In this paper, we present an on-line financial leasing problem considering the second-hand transaction issue, i.e. the equipment can be sold in the secondary market when it is no longer needed. Using competitive analysis, the optimal deterministic strategies are given to deal with the financial leasing problem. Finally, to test the performance of the proposed on-line financial leasing strategies, several numerical experiments are conducted. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The k-cardinality assignment (k-assignment, for short) problem asks for finding a minimal (maximal) weight of a matching of cardinality k in a weighted bipartite graph \(K_{n,n}\) , \(k \le n\) . Here we are interested in computing the sequence of all k-assignments, \(k=1,\ldots ,n\) . By applying the algorithm of Gassner and Klinz (2010) for the parametric assignment problem one can compute in time \({\mathcal {O}}(n^3)\) the set of k-assignments for those integers \(k \le n\) which refer to essential terms of the full characteristic maxpolynomial \({\bar{\chi }}_{W}(x)\) of the corresponding max-plus weight matrix W. We show that \({\bar{\chi }}_{W}(x)\) is in full canonical form, which implies that the remaining k-assignments refer to semi-essential terms of \({\bar{\chi }}_{W}(x)\) . This property enables us to efficiently compute in time \({\mathcal {O}}(n^2)\) all the remaining k-assignments out of the already computed essential k-assignments. It follows that time complexity for computing the sequence of all k-cardinality assignments is \({\mathcal {O}}(n^3)\) , which is the best known time for this problem. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We denote by Leafy Spanning \(k\) -Forest the problem of, given a positive integer k and a graph G with at most k components, finding a spanning forest in G with at most k components and the maximum number of leaves. The case \(k=1\) is known to be NP-hard, and is well studied in the literature, with the best approximation algorithm having been proposed more than 20 years ago by Solis-Oba. The best approximation algorithm known for Leafy Spanning \(k\) -Forest is a 3-approximation based on an approach by Lu and Ravi for the \(k=1\) case. We extend the algorithm of Solis-Oba to achieve a 2-approximation for Leafy Spanning \(k\) -Forest. PubDate: 2022-09-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We explore the problem of scheduling n jobs on a single machine in which there are m fixed machine non-availability intervals. The target is to seek out a feasible solution that minimizes total weighted late work. Three variants of the problem are investigated. The first is the preemptive version, the second is the resumable version, and the third is the non-resumable version. For the first one, we present an \(O((m+n) \log n)\) -time algorithm to solve it. For the second one, we develop an exact dynamic programming algorithm and a fully polynomial time approximation scheme. For the third one, we first demonstrate that it is strongly \(\mathcal{NP}\mathcal{}\) -hard for the case where all jobs have the unit weight and common due date, and then we develop a pseudo-polynomial time algorithm for the unit weight case where the number of non-availability intervals is fixed, finally we propose a pseudo-polynomial time algorithm for the case where there is only one non-availability interval. PubDate: 2022-08-02
Hybrid journal (It can contain Open Access articles)
