The current best-known performance guarantees for the extensively studied Traveling Salesman Problem (TSP) of determinate approximation algorithms is 3/2, achieved by Christofides' algorithm 47 years ago. This pap...
详细信息
The current best-known performance guarantees for the extensively studied Traveling Salesman Problem (TSP) of determinate approximation algorithms is 3/2, achieved by Christofides' algorithm 47 years ago. This paper investigates a new generalization problem of the TSP, termed the Minimum-Cost Bounded Degree Connected Subgraph (MBDCS) problem. In the MBDCS problem, the goal is to identify a minimum-cost connected subgraph containing n = |V| edges from an input graph G = (V, E) with degree upper bounds for particular vertices. We show that for certain special cases of MBDCS, the aim is equivalent to finding a minimum-cost Hamiltonian cycle for the input graph, same as the TSP. To appropriately solve MBDCS, we initially present an integer programming formulation for the problem. Subsequently, we propose an algorithm to approximate the optimal solution by applying the iterative rounding technique to solution of the integer programming relaxation. We demonstrate that the returned subgraph of our proposed algorithm is one of the best guarantees for the MBDCS problem in polynomial time, assuming P not equal N P. This study views the optimization of TSP as finding a minimum-cost connected subgraph containing n edges with degree upper bounds for certain vertices, and it may provide new insights into optimizing the TSP in future research.
We are given a set of m identical parallel machines and a set of n jobs in large computing systems, where each job J(j) consists of a bag of bj identical tasks with a processing time p(j), and has a rejection penalty ...
详细信息
We are given a set of m identical parallel machines and a set of n jobs in large computing systems, where each job J(j) consists of a bag of bj identical tasks with a processing time p(j), and has a rejection penalty wj. Job J(j )is either accepted in which case all the b(j) tasks must be processed by one of the machines, or rejected which incurs a rejection penalty w(j). The problem of bag-of-tasks scheduling with rejection is to find a feasible schedule, so as to minimize the makespan plus the total rejection penalty of all rejected jobs. In this paper, we present a polynomial time approximation scheme.
Adaptive submodular maximization has been extensively studied in the literature. However, most of existing studies in this field focus on pool-based setting, where one is allowed to pick items in any order, and there ...
详细信息
Adaptive submodular maximization has been extensively studied in the literature. However, most of existing studies in this field focus on pool-based setting, where one is allowed to pick items in any order, and there have been few studies for the stream-based setting where items arrive in an arbitrary order and one must immediately decide whether to select an item or not upon its arrival. In this paper, we introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.(c) 2022 Elsevier B.V. All rights reserved.
We consider a generalization of the unsplittable maximum two-commodity flow problem on undirected graphs where each commodity can be split into a bounded number k (i) of equally-sized chunks that can be routed on diff...
详细信息
We consider a generalization of the unsplittable maximum two-commodity flow problem on undirected graphs where each commodity can be split into a bounded number k (i) of equally-sized chunks that can be routed on different paths. We show that in contrast to the single-commodity case this problem is NP-hard, and hard to approximate to within a factor of alpha > 1/2. We present a polynomial time 1/2-approximation algorithm for the case of uniform chunk size over both commodities and show that for even k (i) and a mild cut condition it can be modified to yield an exact method. The uniform case can be used to derive a 1/4-approximation for the maximum concurrent (k (1), k (2))-splittable flow without chunk size restrictions for fixed demand ratios.
Path cover is a well-known intractable problem whose goal is to find a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the objective function is not th...
详细信息
ISBN:
(数字)9783319947761
ISBN:
(纸本)9783319947761;9783319947754
Path cover is a well-known intractable problem whose goal is to find a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the objective function is not the number of paths but the number of length-0 paths (that is, isolated vertices), turns out to be polynomial-time solvable. We further show that another variant, where the objective function is the total number of length-0 and length-1 paths, is also polynomial-time solvable. Both variants find applications in approximating the two-machine flow-shop scheduling problem in which job processing constraints are formulated as a conflict graph. For the unit jobs, we present a 4/3-approximation algorithm for the scheduling problem with an arbitrary conflict graph, based on the exact algorithm for the variants of the path cover problem. For arbitrary jobs where the conflict graph is the union of two disjoint cliques (i.e., all the jobs can be partitioned into two groups such that the jobs in a group are pairwise conflicting), we present a simple 3/2-approximation algorithm.
This paper considers the problem of scheduling multiple two-stage flowshops that minimizes the makespan, where the number of flowshops is part of the input. We study the relationship between the problem and the classi...
详细信息
ISBN:
(纸本)9783319947761;9783319947754
This paper considers the problem of scheduling multiple two-stage flowshops that minimizes the makespan, where the number of flowshops is part of the input. We study the relationship between the problem and the classical MAKESPAN problem. We prove that if there exists an a-approximation algorithm for the MAKESPAN problem, then for the multiple two-stage flowshop scheduling problem, we can construct a 2 alpha-approximation algorithm for the general case, and (alpha+1/2)-approximation algorithms for two restricted cases. As a result, we get a (2+epsilon)-approximation algorithm for the general case and a (1.5 + epsilon)-approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2.6 and 11/6, respectively.
Motivated by the increasing number of drones used for package delivery, we first study the problem of Multiple drOne collaborative Routing dEsign (MORE) in this article. That is, given a fixed number of drones and cus...
详细信息
Motivated by the increasing number of drones used for package delivery, we first study the problem of Multiple drOne collaborative Routing dEsign (MORE) in this article. That is, given a fixed number of drones and customers, determining the delivery trip for drones under capacity constraint with stochastic demand for customers such that the overall expected traveling cost is minimized. To address the MORE problem, we first prove that MORE falls into the realm of the classical vehicle routing problem with stochastic demand and then propose an effective algorithm for MORE. Next, we have a scheme of resplitting customers into different individual delivery trips while the stochastic demands are determined. Moreover, we consider a variety of MORE, MORE-TW, and design an effective algorithm to address it. We conduct simulation experiments for MORE to verify our theoretical findings. The results show that our algorithm outperforms other comparison algorithms by at least 79.60%.
This paper investigates the three-stage assembly flow shop scheduling problem, provided that there is a fixed maintenance period (MP) imposed on one of the machines in the first stage, the objective is to minimize the...
详细信息
This paper investigates the three-stage assembly flow shop scheduling problem, provided that there is a fixed maintenance period (MP) imposed on one of the machines in the first stage, the objective is to minimize the makespan. The starting time and duration of MP are known in advance, during MP no job can be processed on the corresponding machine. Only the non-resumable scenario is considered, i.e., if a job fails to finish before MP, it must restart from the beginning after the machine becomes available again, rather than continuing its processing. The problem generalizes the three-stage assembly flow shop scheduling problem without MPs and is therefore strongly NP-hard. To the best of our knowledge, the problem has not been explored so far. We propose three approximation algorithms for the problem.
We study the problem of augmenting a metric graph by adding k edges while minimizing the radius of the augmented graph. We give a simple 3-approximation algorithm and show that there is no polynomial-time (5/3 - e)-ap...
详细信息
We study the problem of augmenting a metric graph by adding k edges while minimizing the radius of the augmented graph. We give a simple 3-approximation algorithm and show that there is no polynomial-time (5/3 - e)-approximation algorithm, for any e > 0, unless P =N *** also give two exact algorithms for the special case when the input graph is a tree, one of which is generalized to handle metric graphs with bounded treewidth.
Given a graph G with vertex set V, a set S subset of V is a secure dominating set of G if S is a dominating set of G and if for every vertex u is an element of V \ S, there exists a vertex v is an element of S adjacen...
详细信息
Given a graph G with vertex set V, a set S subset of V is a secure dominating set of G if S is a dominating set of G and if for every vertex u is an element of V \ S, there exists a vertex v is an element of S adjacent to u such that (S boolean OR {u}) \ {v} is a dominating set of *** minimum secure dominating set (or, for short, MSDS) problem asks to find an MSDS in a given graph. In this paper, we first show that the decision version of the MSDS problem is NP-complete in unit disk graphs, even in grid graphs. Secondly, we give an O(n + m) time t-approximation algorithm for the MSDS problem in several geometric intersection graphs which are K1,t-free for some integer t >= 3. Finally, we propose a PTAS for the MSDS problem in unit disk graphs.(c) 2023 Elsevier Inc. All rights reserved.
暂无评论