Search

We improve the approximation ratio for Maximum Weight Series-Parallel Subgraph from 1 / 2 to 1 / 2 + 1 / 60. [ABSTRACT FROM AUTHOR]

In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B + 1) -approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network. [ABSTRACT FROM AUTHOR]

We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2 / 3. We propose a new approximation algorithm which improves the ratio to 7 / 10. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , an L (2 , 1) -labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u , v) , | ℓ (u) − ℓ (v) | ≥ 2 if u and v are adjacent, and ℓ (u) ≠ ℓ (v) if u and v are at distance 2. The L (2 , 1) -labeling problem is to minimize the range of ℓ (i.e., max u ∈ V (ℓ (u)) − min u ∈ V (ℓ (u)) + 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L (2 , 1) -labeling of unit disk graphs. • An 8-approximation algorithm of L(2,1)-labeling for unit disk graphs with geometric representations is presented. • The previously known bound is 10.67. • The presented algorithm gives a simple periodic labeling based on a new way of partitioning the plane into squares. [ABSTRACT FROM AUTHOR]

We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7 / 3. This allows us to derive a 7 / 3 -approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach. [ABSTRACT FROM AUTHOR]

The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum b -matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the k -degenerate graphs, whose approximation ratios are α + 2 k − 2 and α k , where α is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an (α + k) -approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are k -systems with independence oracles. [ABSTRACT FROM AUTHOR]

The squared metric k -facility location problem is a frequently encountered generalization of the k -means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44.473 + ϵ , which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36.342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric. • We give a (36.342 + ϵ) -approximation algorithm for the squared metric k -facility location problem. • We obtain a well-behaved fractional solution to the squared metric k -facility location problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach that exploits the properties of the squared metric. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

We investigate two parallel dedicated machine scheduling with conflict constraints. The problem of minimizing the makespan has been shown to be NP-hard in the strong sense under the assumption that the processing sequence of jobs on one machine is given and fixed a priori. The problem without any fixed sequence was previously recognized as weakly NP-hard. In this paper, we first present a 9 5 -approximation algorithm for the problem with a fixed sequence. Then we show that the tight approximation ratios of the algorithm are 7 4 and 5 3 for two subproblems which remain strongly NP-hard. We also send an improved algorithm with approximation ratio 3 − 2 ≈ 1.586 for one subproblem. Finally, we prove that the problem without any fixed sequence is actually strongly NP-hard, and design a 5 3 -approximation algorithm. • Consider the problem of scheduling with conflict constraints on two parallel dedicated machines. • Present a 9 5 -approximation algorithm for the strongly NP-hard case where jobs on one machine have a fixed processing sequence, and give improvements to its hard subproblems. • Prove that the problem without any fixed sequence is strongly NP-hard too and propose a 5 3 -approximation algorithm. [ABSTRACT FROM AUTHOR]

The rooted Budgeted Cycle Cover (BCC) problem is a fundamental optimization problem arising in wireless sensor networks and vehicle routing. Given a metric space (V , w) with vertex set V consisting of two parts D (containing depots) and V ∖ D (containing nodes), and a budget B ≥ 0 , the rooted BCC problem asks to find a minimum number of cycles to cover all the nodes in V ∖ D , satisfying that each cycle has length at most B and each cycle must contain a depot in D. In this paper, we give new approximation algorithms for the rooted BCC problem. For the rooted BCC problem with single depot, we give an O (log ⁡ B μ) -approximation algorithm, where μ is the minimum difference of any two different distances between the vertices in V and the root. For the rooted BCC problem with multiple depots, we give an O (log ⁡ n) -approximation algorithm, where n is the number of vertices. We also test our algorithms on the randomly generated instances. The experimental results show that the algorithms have good performance in practice. • A log-factor approximation algorithm for the single depot budgeted cycle cover problem. • A log-factor approximation algorithm for the multi-depot budgeted cycle cover problem. • Experiments on randomly generated instances show good performance of the algorithms. [ABSTRACT FROM AUTHOR]

In this work we investigate the problem of estimating the percolation centrality of all vertices in a weighted graph. The percolation centrality measure quantifies the importance of a vertex in a graph that is going through a contagious process. The fastest exact algorithm for the computation of this measure in a graph G with n vertices and m edges runs in O (n 3). Let Diam V (G) be the maximum number of vertices in a shortest path in G. In this paper we present an expected O (m log n log Diam V (G)) time approximation algorithm for the estimation of the percolation centrality for all vertices of G. We show in our experimental analysis that in the case of real-world complex networks, the output produced by our algorithm returns approximations that are even closer to the exact values than its guarantee in terms of theoretical worst case analysis. [ABSTRACT FROM AUTHOR]

Given a complete undirected graph G = (V , E) , where V is the vertex set partitioned into K clusters V 1 , V 2 , ... , V K and E is the edge set with edge weights satisfying triangle inequality, and a positive integer k , the min-max clustered k-traveling salesmen problem (min-max C k -TSP) asks to find a set of k tours to visit all vertices, such that each cluster is visited by exactly one tour and the vertices of each cluster are visited consecutively. The objective is to minimize the weight of the maximum weight tour. The problem is known to be NP-hard even when k = 1 and K = 1. In this paper, we consider two variants of the problem. The first one is all the k tours have a common predefined starting vertex, and the other one is no starting vertex of any tour is specified. For both the variants we propose the first constant-factor approximation algorithms with ratios 5.5 and 16, respectively. • We consider the min-max clustered k-traveling salesmen problem. • We propose a 5.5-approximation algorithm for the case in which all the k tours have a common predefined starting vertex. • We provide a 16-approximation algorithm for the case in which no starting vertex of any tour is specified. • Both algorithms are the first constant-factor approximation algorithms. [ABSTRACT FROM AUTHOR]

In the capacitated facility location problem, we are given a set F of potential facilities and a set D of clients, where each facility has a capacity and an open cost, and each client has a demand to be served by the facilities with service costs. The goal is to open some facilities in F and assign all clients in D to these open facilities such that the total cost is minimum. Based on the natural integer programming formulation, Levi et al. [8] presented an LP-based 5-approximation algorithm for this problem under the assumption that the facility costs are uniform. Based on the same integer programming formulation, we remove the uniformity assumption and present an (R + R 2 + 8 R 2 + 3) -approximation algorithm for the capacitated facility location problem, where R is the upper bound of the ratio between facility costs. Our result is a slight extension of the corresponding result in [8] , as when R = 1 the worst-case ratio of our algorithm is R + R 2 + 8 R 2 + 3 = 5. [ABSTRACT FROM AUTHOR]

In this work we introduce the Minimum Rural Postmen Cover Problem (MRPCP) and the Minimum Chinese Postmen Cover Problem (MCPCP). The MRPCP aims to cover a given subset R of edges of an undirected weighted graph G = (V , E) by a minimum size set of closed walks of bounded length λ. The MCPCP is a special case of the MRPCP with R = E. We give the first approximation algorithms for these two problems, which have constant approximation ratios of 5 and 4, respectively. [ABSTRACT FROM AUTHOR]

The anti-Ramsey number , a r (G , H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H , namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdös and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q -colouring problem: Find a colouring of the edges of G , maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals a r (G , K 1 , q + 1) − 1. In this paper, we study the maximum edge 2-colouring problem from the approximation algorithm point of view. The case q = 2 is particularly interesting due to its application in real-life problems. Algorithmically, this problem is known to be NP-hard for q ≥ 2. For the case of q = 2 , it is also known that no polynomial-time algorithm can approximate to a factor less than 3 / 2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5 / 3 -approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G ∖ M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8 / 5. We also show that this algorithm cannot achieve a factor better than 58 / 37 on triangle free graphs that has a perfect matching. The contribution of the paper is a completely new, deeper and closer analysis of how the optimum achieves a higher number of colours than the matching based algorithm, mentioned above. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple undirected graph. A set D ⊆ V is called a vertex-edge dominating set of G if for each edge e = u v ∈ E , either u or v is in D or one vertex from their neighbor is in D. Simply, a vertex v ∈ V , vertex-edge dominates every edge u v , as well as every edge adjacent to these edges. The objective of the vertex-edge domination problem is to find a minimum size vertex-edge dominating set of G. Herein, we study the vertex-edge domination problem in unit disk graphs and prove that the decision version of the problem belongs to the NP-complete class. We also show that the problem admits a simple polynomial-time 4-factor approximation algorithm and a polynomial-time approximation scheme (PTAS) in unit disk graphs. [ABSTRACT FROM AUTHOR]

Given a set of vehicles that are allowed to move in a plane along a predefined directed rectilinear path, the collision-free routing problem seeks a maximum number of vehicles that can move without collision. This problem is known to be NP-hard (Ajaykumar et al., 2016). Here we study a variant of this problem called the constrained collision-free routing problem (in short, CCRP). In this problem, each vehicle is allowed only to move in a directed L-shaped path. First, we show that CCRP is NP-hard. Further, we prove that any β -approximation algorithm for the maximum independent set problem in B 1 -VPG graphs would produce a β -approximation for CCRP. Also, we propose a 2-approximation algorithm for the maximum independent set problem on intersection graph of n unit-L frames (the union of a unit-length vertical and a unit-length horizontal line segment that shares an endpoint) with O (n) space and O (n 2) time. [ABSTRACT FROM AUTHOR]

Consider a Gaussian downlink between an access point with power budget P > 0 , and a set of users specified by their effective noises and rate demands. In order to control the decoding complexity and error propagation, an integer-valued access limit M > 0 is imposed on the number of superimposed users. For each subset S of users, its (total) power demand p (S) is a strictly increasing and nonseparable function of the effective noises and rate demands of users in S. A subset S of users is feasible if | S | ≤ M and p (S) ≤ P. The goal is to select a feasible subset S of users whose total rate demand is maximized. In this paper, we show that this problem is NP-hard, and present a (1 − 1 / e) -approximation algorithm for this problem. In addition, we also give several other approximation algorithms with trade-offs between accuracy and efficiency. • The Gaussian downlink user selection problem studied in this paper is an NP-hard maximization problem. • The first 1 2 (1 − 1 / e) -approximation algorithm takes the relaxation/extraction approach. • A better algorithm utilizes partial enumeration for reducing the extraction loss, and achieves (1 − 1 / e) -approximation factor. • The paper is concluded with a summary of the general algorithmic framework and some open problems for further studies. [ABSTRACT FROM AUTHOR]

What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v , the opening cost of v is at most θ times the service cost of u ? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G = (V , E) , a set R ⊆ V of terminals, and thresholds { t u e , t v e } for each uv -edge e ∈ E. The goal is to find an assignment a = { a v : v ∈ V } to the nodes minimizing ∑ v ∈ V a v , such that the edge set E a = { e = u v : a u ≥ t u e , a v ≥ t v e } activated by a covers R. We obtain ratio 1 + max x ≥ 1 ⁡ ln ⁡ x 1 + x / θ ≈ ln ⁡ θ − ln ⁡ ln ⁡ θ for the problem, where θ ≤ max e ∈ E ⁡ max ⁡ { t u e , t v e } min ⁡ { t u e , t v e } is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of Facility Location. If for each facility all service costs are identical then we show a better ratio 1 + max k ∈ N ⁡ H k − 1 1 + k / θ , where H k = ∑ i = 1 k 1 / i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [4] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73 / 60 ≈ 1.217 of [4] to 1555 1347 ≈ 1.155. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G = (V , E) is a subset of vertices S ⊆ V such that every vertex v ∈ V ∖ S has at least one neighbor in S. Finding a dominating set with the minimum cardinality in a connected graph G = (V , E) is known to be NP-hard. A polynomial-time approximation algorithm for this problem, described here, works in two stages. At the first stage a dominant set is generated by a greedy algorithm, and at the second stage this dominating set is purified (reduced). The reduction is achieved by the analysis of the flowchart of the algorithm of the first stage and a special kind of clustering of the dominating set generated at the first stage. The clustering of the dominating set naturally leads to a special kind of a spanning forest of graph G , which serves as a basis for the second purification stage. We expose some types of graphs for which the algorithm of the first stage already delivers an optimal solution and derive sufficient conditions when the overall algorithm constructs an optimal solution. We give three alternative approximation ratios for the algorithm of the first stage, two of which are expressed in terms of solely invariant problem instance parameters, and we also give one additional approximation ratio for the overall two-stage algorithm. The greedy algorithm of the first stage turned out to be essentially the same as the earlier known state-of-the-art algorithms for the set cover and dominating set problem Chvátal [6] and Parekh [31]. The second purification stage results in a significant reduction of the dominant set created at the first stage, in practice. The practical behavior of both stages was verified for randomly generated problem instances. The computational experiments emphasize the gap between a solution of Stage 1 and a solution of Stage 2. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a subset D of vertex set V , is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set) , if the subgraph induced by D in G has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem is NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the other side, the problem is efficiently solvable for many graph classes including interval graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graphs. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (2015) [19] and (2020) [20]. Alvarado et al. (2015) [1] conjectured that given a graph G = (V , E) , it is NP-hard to decide whether γ (G) = γ p r (G). In this paper we settle this conjecture affirmatively. [ABSTRACT FROM AUTHOR]

• Propose a new problem: prize-collecting sweep cover problem. • Give a 5-LMP algorithm for prize-collecting sweep cover assuming constant number of base-stations. • Give a 2-LMP algorithm for the rooted prize-collecting forest with k components problem. In a sweep cover problem, positions of interest (PoIs) are required to be visited periodically by mobile sensors. In this paper, we propose a new sweep cover problem: the prize-collecting sweep cover problem (PCSC), in which penalty is incurred by those PoIs which are not sweep-covered, and the goal is to minimize the covering cost plus the penalty. Assuming that every mobile sensor has to be linked to some base station, and the number of base stations is upper bounded by a constant, we present a 5-LMP (Lagrangian Multiplier Preserving) algorithm. As a step stone, we propose the prize-collecting forest with k components problem (PCF k), which might be interesting in its own sense, and presented a 2-LMP for rooted PCF k. [ABSTRACT FROM AUTHOR]

The influence maximization problem aims to find some seeds which can cause the maximum influence spread results in a social network. Most researches focus on the non-adaptive strategies, in which all seeds are selected at once. For the non-adaptive strategies, the seeds may influence other seeds in the influence spread process and make the waste of budget. This paper considers the adaptive strategies and studies the adaptive influence maximization and adaptive stochastic influence maximization in the general feedback model. These problems select seeds adaptively, and it completes each selection after the fixed observation time-step. In this paper, we utilize the adaptive greedy to solve these problems and propose a theoretical analysis by introducing a comparative factor. In addition, we present the feasible approximation algorithm using the reverse sampling technique. Finally, we carry out experiments on three networks to show the efficiency of adaptive strategies. • We study the adaptive influence maximization problem under a general model. • We propose a comparative factor and obtain the approximation ratio of an adaptive greedy algorithm. • We not only consider the problem with cardinality constraint but also the knapsack constraint. • We conduct several experiments on three real datasets to show the effectiveness of adaptive methods. [ABSTRACT FROM AUTHOR]

Damian and Pemmaraju (2002) [8] introduced leaf sector covers for circle graphs and presented an O (n 2) -time algorithm to find this data structure. They subsequently employed it as an algorithmic tool, leading to the development of an 8-approximation algorithm for the dominating set problem, a (2 + ε) -approximation scheme for the dominating set problem, and a (3 + ε) -approximation scheme for the total dominating set problem. In this paper, we have improved the time complexity from O (n 2) to O (n + m) for finding a leaf sector cover. Furthermore, we employed leaf sector covers as a powerful algorithmic tool to design a 10-approximation algorithm for the total dominating set problem and a 12-approximation algorithm for the paired-dominating set problem. Moreover, we also proposed a (2 + ε) -approximation scheme for the total dominating set problem and a (4 + ε) -approximation scheme for the paired-dominating set problem. The results presented above are currently the best algorithms for circle graphs. [ABSTRACT FROM AUTHOR]

• We introduce the minimum power cover problem with submodular and linear penalties. • We present a combinatorial primal-dual approximation algorithm for the minimum power cover problem with submodular penalties. • We present a polynomial time approximation scheme for the minimum power cover problem with linear penalties. In this paper, we introduce the minimum power cover problem with submodular and linear penalties. Suppose U is a set of users and S is a set of sensors in a d -dimensional space R d with d ≥ 2. Each sensor can adjust its power and the relationship between the power p (s) and the radius r (s) of the service area of sensor s satisfies p (s) = c ⋅ r (s) α , where c > 0 and α ≥ 1. Let p be the power assignment for each sensor and R be the set of users who are not covered by any sensor supported by p. The objective is to minimize the total power of p plus the rejected penalty of R. For a submodular penalty function that is normalized and nondecreasing, we present a combinatorial primal-dual (3 α + 1) -approximation algorithm. For the case in which the submodular penalty function is linear, we present a polynomial time approximation scheme based on a plane subdivision technique. [ABSTRACT FROM AUTHOR]

• Research was motivated from recent research in cloud computing. • A new model for research on scheduling of multiple processors. • Computational complexity of the proposed scheduling problems. • Approximation algorithms for the proposed scheduling problems. • Relationship between the proposed scheduling problems and multiple knapsack packing. Recently, motivated by applications in cloud computing, scheduling multiple two-stage flowshops with the objective of minimizing the makespan has drawn increasing attention. Motivated by the same applications, the current paper studies the problem of scheduling multiple two-stage flowshops with a deadline, with the objective of maximizing the profit of the jobs that can be completed by the deadline. Algorithms and complexity of the problem are investigated. For the case where the number of two-stage flowshops is part of the input, we present an efficient approximation algorithm with a constant ratio. The approximation ratio is improved via a study of the relationship between the problem and the multiple knapsack problem, combined with the recent progresses in the research in approximation algorithms for the multiple knapsack problem. By integrating techniques in the study of the classical Knapsack problem and the classical Makespan problem on multiple processors, plus additional new techniques, a polynomial-time approximation algorithm with a further improved approximation ratio is developed for the case where the number of flowshops is a fixed constant. [ABSTRACT FROM AUTHOR]

The support of a flow x in a network is the subdigraph induced by the arcs uv for which x (u v) > 0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N = (D , s , t , c) has a maximum flow x such that the maximum out-degree of the support D x of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p -path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a p -path-flow x whose value is at least 2 3 of the value of a optimum p -path-flow when p ∈ { 2 , 3 } , and at least 1 2 when p ≥ 4. When p = 2 , they show that this is best possible unless P=NP. We show for each p ≥ 2 that the value of a maximum p -path-flow cannot be approximated by any ratio larger than 9 11 , unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor 1 H (p) of the optimum solution, where H (p) is the p 'th harmonic number (H (p) ∼ ln ⁡ (p)). We show that in the case where the network is acyclic, we can find such a maximum p -path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible. [ABSTRACT FROM AUTHOR]

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study multiple drone delivery scheduling problem (MDSP) [1] for last-mile delivery, where we have a set of drones with an identical battery budget and a set of delivery locations; along with profit for delivery, cost, and delivery time intervals. The objective of the MDSP is to find conflict-free schedules for each drone such that the total profit gained is maximum subject to the battery constraint of the drones. This paper proposes an optimal pseudo-polynomial algorithm and a fully polynomial time approximation scheme (FPTAS) for the single drone delivery scheduling problem (SDSP). Also, we propose two approximation algorithms of factor 1 3 for the MDSP with some constraints on the number of drones. We formulate the problem for the heterogeneous case, where the drones have non-identical battery capacities, and propose a 1 6 ρ -approximation algorithm, where ρ is the ratio between the minimum and maximum battery capacity of the drones. • An optimal pseudo-polynomial algorithm and FPTAS for the single drone delivery scheduling problem is proposed. • Two approximation algorithms for the multiple drone delivery scheduling problem are proposed. • An approximation algorithm for the multiple heterogeneous drone delivery scheduling problem is proposed. • We analyzed the approximation factors of all the aforementioned proposed algorithms and time complexities. [ABSTRACT FROM AUTHOR]

The anti-Ramsey number a r (G , H) with input graph G and pattern graph H , is the maximum positive integer k such that there exists an edge coloring of G using k colors, in which there are no rainbow subgraphs isomorphic to H in G. (H is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdős et al. in 1973. Thereafter, several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph K 1 , t (for t ≥ 3) purely from an algorithmic point of view. For a graph G and an integer q ≥ 2 , an edge q -coloring of G is an assignment of colors to edges of G , such that the edges incident on a vertex span at most q distinct colors. The maximum edge q-coloring problem seeks to maximize the number of colors in an edge q -coloring of the graph G. Note that the optimum value of the edge q -coloring problem of G equals a r (G , K 1 , q + 1). Here, we study a r (G , K 1 , t) , the anti-Ramsey number of stars, for each fixed integer t ≥ 3 , both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for a r (G , K 1 , q + 1) , in terms of number of vertices and the minimum degree of G. The second one improves this result for the case of triangle-free input graphs. Our third main result presents an upper bound for a r (G , K 1 , q + 1) in terms of | E (G ≤ (q − 1)) | , which is a frequently used lower bound for a r (G , K 1 , q + 1) and maximum edge q -coloring in the literature. All our results have algorithmic consequences. [ABSTRACT FROM AUTHOR]

In large-scale disasters, evacuation using public transport, such as buses, is always essential, especially with limitations on the time window and resources available. Unfortunately, a Bus Evacuation Problem (BEP) is NP-hard in nature. This means it is impossible to find an optimal evacuation plan within a reasonable time window. Therefore, it is efficacious and requisite to use an approximation algorithm such that a sub-optimal plan can be derived quickly in large-scale disasters. In the literature, an approximation algorithm for BEP has been presented. However, there is not only a lack of rigorous proof of the approximation ratio, but also the computation time of the approximation algorithm is influenced by the number of evacuees. In this work, firstly the approximation ratio is derived as 2 n b + 7 , where n b is the number of buses, which is fundamentally more precise than the existing work. Further, the approximation ratio can be reduced to n b + 6 through a new proof provided in this work. More importantly, a new approximation algorithm is proposed in this work, with an aggregated network flow model that can be quickly solved as a linear programming problem in polynomial time. The approximation ratio of the new algorithm is proven to be n b + 1 when there is a pile of buses, and the computation time is insensitive to the number of evacuees. Finally, 10 sets of random cases and a real-life disaster, the flooding in Xingguo, China in 2019 are studied to illustrate the efficiency and practical applicability of the proposed approximation algorithm. [ABSTRACT FROM AUTHOR]

We consider 2-connectivity network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. • In the 1 -Connectivity Augmentation problem the goal is to augment a connected graph by a minimum size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural approximation ratio 2 for this problem, and also for the more general Crossing Family Cover problem. • In the 2 -Connected Dominating Set problem, we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm with expected approximation ratio O (σ (n) ⋅ log 3 ⁡ n) , where σ (n) = O (log ⁡ n ⋅ log ⁡ log ⁡ n ⋅ (log ⁡ log ⁡ log ⁡ n) 3). The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems. [ABSTRACT FROM AUTHOR]

We consider the maximum vertex-weighted matching problem (MVM) for non-bipartite graphs in which non-negative weights are assigned to the vertices of a graph and a matching that maximizes the sum of the weights of the matched vertices is desired. In earlier work we have described a 2 / 3 -approximation algorithm for the MVM on bipartite graphs (Florin Dobrian et al., 2019). Here we show that a 2 / 3 -approximation algorithm for MVM on non-bipartite graphs can be obtained by restricting the length of augmenting paths to at most three. The algorithm has time complexity O (m log Δ + n log n) , where n is the number of vertices, m is the number of edges, and Δ is the maximum degree of a vertex. The approximation ratio of the algorithm is obtained by considering failed vertices , i.e., vertices that the approximation algorithm fails to match but the exact algorithm does. We show that there are two distinct heavier matched vertices that we can charge each failed vertex to. Our proof techniques characterize the structure of augmenting paths in a novel way. We have implemented the 2 / 3 -approximation algorithm and show that it runs in under a minute on graphs with tens of millions of vertices and hundreds of millions of edges. We compare its performance with five other algorithms: an exact algorithm for MVM, an exact algorithm for the maximum edge-weighted matching (MEM) problem, as well as three approximation algorithms. The approximation algorithms include a 1 / 2 -approximation algorithm for MVM, and (2 / 3 − ε) - and (1 − ε) -approximation algorithms for the MEM. In our test set of nineteen problems, there are graphs on which the exact algorithms fail to terminate in 100 hours. In addition, the new 2 / 3 -approximation algorithm for MVM outperforms the other approximation algorithms by either being faster (often by orders of magnitude) or obtaining better weights. [ABSTRACT FROM AUTHOR]

A cooperative truck platoon is a set of virtually linked trucks driving with a small intra-vehicle headway enabled by connected and automated vehicle technologies. One of the primary benefits of truck platooning is energy savings due to the reduction of aerodynamic drag on the platooned vehicles. The focus of this paper is on scheduling travel itineraries of a given set of trucks to facilitate the formation of platoons to maximize energy savings. By constructing a time-expanded network, we formulate the problem as a minimum concave-cost network flow problem, and devise a few solution methods to find the optimal or high-quality solutions. The solution methods include an outer approximation algorithm for solving a mixed-integer convex minimization reformulation of the problem, a dynamic-programming-based heuristic scalable to large-scale instances, and a fast approximation algorithm with guaranteed performance for a restrictive version of the problem. All the proposed algorithms are examined and benchmarked on medium to large networks under various test scenarios. The numerical results demonstrate the efficiency of the proposed methods and their applicability in real-world settings. • Formulate truck platooning planning as a minimum concave-cost network flow problem. • Develop a hybrid outer approximation/local search algorithm for medium-sized problems. • Propose a dynamic-programming-based heuristic for large-scale problems. • Devise an approximation algorithm for a special-case truck platooning problem. [ABSTRACT FROM AUTHOR]

• Present a deterministic approximation algorithm for submodular maximization with a curvature parameter α. • Generalize the previous deterministic 0.5008-approximation due to Buchbinder et al., achieving an identical ratio of 0.5008 when α = 1. • Achieve a ratio of 1 for α = 0 for which the function is actually linear that the problem is polynomial solvable. • Devise more sophisticated analysis on the inequalities about monotonicity with curvature via mathematical tools such as infinite series. In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0 , 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1. For general value of the curvature parameter α ∈ [ 0 , 1 ] , we present an approximation algorithm with a factor of 1 + h α (y) + Δ ⋅ [ 3 + α − (2 + α) y − (1 + α) h α (y) ] 2 + α + (1 + α) (1 − y) , where y ∈ [ 0 , 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0.5008 when setting y = 0.9 , coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions. [ABSTRACT FROM AUTHOR]

The input to a PPNC instance is integers n and p , and a non-negative real weighting of the edges of the clique K n on the vertex set {1,..., n }. We are asked to find a set of p disjoint cycles spanning {1,..., n } and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p. For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T -join With Slack problem. The input to an instance of Mod k T -join with Slack consists of integers n and B , a non-negative weighting of the edges of the clique K n , and a label l(v) from {0,1,..., k - 1} on each vertex of K n. We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑ T∈F ((∑ v∈V(T) l(v)) mod k) ≤ B. If k = 2 and B = 0 this is the well-studied T -join problem which can be solved exactly in polynomial time. [ABSTRACT FROM AUTHOR]

• A new seeding algorithm is proposed for the fuzzy C-means problem. • Theoretical guarantees for both the new seeding algorithm and the fuzzy C-means++ algorithm are given. • Numerical experiments show the effectiveness of the new algorithm. As a kind of important soft clustering model, the fuzzy C -means method is widely applied in many fields. In this method, instead of the strict distributive ability in the classical k -means method, all the sample points are endowed with degrees of membership to each center to depict the fuzzy clustering. In this paper, we show that the fuzzy C -means++ algorithm, which introduces the k -means++ algorithm as a seeding strategy, gives a solution for which the approximation guarantee is O (k 2 ln ⁡ k). A novel seeding algorithm is then designed based on the contribution of the fuzzy potential function, which improves the approximation ratio to O (k ln ⁡ k). Preliminary numerical experiments are proposed to support the theoretical results of this paper. [ABSTRACT FROM AUTHOR]

We consider a two-stage production scheduling problem where each operation can be outsourced or processed in-house. For each operation in the same machine, the ratio of its outsourcing cost to its processing time is constant. The objective is to minimize the sum of the makespan and the total outsourcing cost. It is known that this problem is either polynomial time solvable or NP-hard according to the conditions of the ratios. Even though approximation algorithms for NP-hard cases had been developed, their tight worst-case performance ratios are still open. In this paper, we carefully analyze the approximation algorithms to identify their tight worst-case performance ratios for cases. In one case, we propose a new approximation algorithm with a better and tight worst-case performance ratio. In the process of analyzing the algorithm, we propose a technique utilizing nonlinear optimization. [ABSTRACT FROM AUTHOR]

• A min number of edge rotations transforming a graph of order n into a k -degree-anonymous. • NP-hard for k = n / q , q ≥ 3. • Polynomial-time 2-approximable under some constraints. • Polynomial-time solvable when k = n and for trees when k = θ (n). The Min Anonymous-Edge-Rotation problem asks for an input graph G and a positive integer k to find a minimum number of edge rotations that transform G into a graph such that for each vertex there are at least k − 1 other vertices of the same degree (a k -degree-anonymous graph). In this paper, we prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k = n / q , where n is the order of a graph and q any positive integer, q ≥ 3. We argue that under some constrains on the number of edges in a graph and k , Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Furthermore, we show that the problem is solvable in polynomial time for any graph when k = n and for trees when k = θ (n). Additionally, we establish sufficient conditions for an input graph and k such that a solution for Min Anonymous-Edge-Rotation exists. [ABSTRACT FROM AUTHOR]

• Scheduling problem on m identical speed scalable processors with shared memory is considered. • A constant approximation algorithm is given. • An optimal algorithm is given when assignment of jobs is fixed. Energy efficiency is a crucial desideratum in the design of computer systems, from small-sized mobile devices with limited battery to large scale data centers. In such computing systems, processors and memory are considered as two major power consumers among all the system components. One recent trend to reduce power consumption is using shared memory in multi-core systems, such architecture has become ubiquitous nowadays. However, implementing the energy-efficient methods to the multi-core processor and the shared memory separately is not trivial. In this work, we consider the energy-efficient task scheduling problem, which coordinates the power consumption of both the multi-core processor and the shared memory, especially focus on the general situation in which the number of tasks is more than the number of cores. We devise an approximation algorithm with guaranteed performance in the multiple cores system. We tackle the problem by first presenting an optimal algorithm when the assignment of tasks to cores is given. Then we propose an approximation assignment for the general task scheduling. [ABSTRACT FROM AUTHOR]

Given a metric graph G = (V , E , w) and an integer k , we aim to find a single allocation k -hub location, which is a spanning subgraph consisting of a clique of size k such that every node outside of the clique is adjacent to exactly one node inside the clique. For various objective functions studied in the literature, we present improved hardness and approximation results. • Consider single allocation hub location problems with six different objectives. • For each problem we achieve improved hardness and/or approximability results. • For five of the six problems we present improved approximation algorithms. [ABSTRACT FROM AUTHOR]

The fair k -median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fairness violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. To our best knowledge, there is no available approximation algorithm for this problem without any fairness violation in doubling metrics. In this paper, we consider the fair k -median problem in doubling metrics and general metrics. We provide the first QPTAS for the fair k -median problem based on the hierarchical decomposition and dynamic programming process in doubling metrics. For applying a dynamic programming process to solve this problem, the distances from portals to facilities cannot be directly enumerated since each client may not be assigned to its closest open facility. To overcome the difficulties caused by the fairness constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get the cost between the portals of each block and the ones in its children. In order to satisfy the fairness constraints, we bound the fairness constraints of each open facility in the leaves of the split-tree based on the relation between the subproblem and the subproblems of its children. To obtain the assignment of the given instance and remove the fairness violation, we construct a new b -value min-cost max-flow model based on the set of open facilities. For the fair k -median problem in general metrics, we present a polynomial-time approximation algorithm with ratio O (log ⁡ k). Our approximation algorithm for the fair k -median problem in doubling metrics is the first result for the corresponding problem without any fairness violation in doubling metrics. [ABSTRACT FROM AUTHOR]

A k -submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k -submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O (n 2 k). We show that Greedy+Singleton has an approximation ratio of 0.273 for monotone functions, which improves the previous analysis of 0.158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k -submodular functions, and prove an approximation ratio of 0.219. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the diversity-aware fair k -supplier problem, which involves selecting k facilities from a set F that consists of m disjoint groups, subject to a constraint on the maximum number of facilities selected from each group. The goal is to ensure fairness in the selection process and avoids any demographic group from over-representation. While the classical k -supplier problem is known to be NP-hard to solve and is even NP-hard to approximate within a factor of less than 3, we present an efficient 5-approximation algorithm for the diversity-aware k -supplier problem based on maximum matching. [ABSTRACT FROM AUTHOR]

This paper considers the high-dimensional table compression problem on balanced k -partite graph. The objective is to choose half of the vertices from each of the k -partite to maximize the total weight of edges connecting the chosen vertices. Our main contribution is a 0.8785-approximation algorithm for the high-dimensional table compression problem by introducing the α - i n d e p e n d e n t solutions through Lasserre semidefinite programming. This new algorithm improved two previous low-dimensional results, namely the 0.8731-approximation algorithm of Wu et al. for the one-dimensional case and the 0.6708-approximation of Xu and Du for the two-dimensional case. [Display omitted] • Present a 0.8785-approximation algorithm for high-dimensional table compression problem. • Obtain a group of independent optimal solutions through Lasserre hierarchy semidefinite programming. • The integer solutions to the original problem are obtained through deformed random hyperplane recognition. [ABSTRACT FROM AUTHOR]

The Gromov-Hausdorff distance (d G H) proves to be a useful distance measure between shapes. In order to approximate d G H for X , Y ⊂ R d , we look into its relationship with d H , i s o , the infimum Hausdorff distance under Euclidean isometries. As already known for dimension d ≥ 2 , d H , i s o cannot be bounded above by a constant factor times d G H. For d = 1 , however, we prove that d H , i s o ≤ 5 4 d G H. We also show that the bound is tight. In effect, for X , Y ⊂ R with at most n points, this gives rise to an O (n log ⁡ n) -time algorithm to approximate d G H (X , Y) with an approximation factor of (1 + 1 4). [ABSTRACT FROM AUTHOR]

• Show that every interval graph G has an equitable tree- k -coloring for any integer k ≥ ⌈ Δ (G) + 1 / 2 ⌉. • Design linear algorithm for proper interval graphs. • Prove the NP-hardness of the problems. • Design a quadratic 2-approximation algorithm for the equitable tree coloring problem in chordal graphs. • Prove that the problem has no α -approximation algorithm for any α < 3 2. An equitable tree- k -coloring of a graph is a vertex k -coloring such that each color class induces a forest and the size of any two color classes differs by at most one. In this work, we show that every interval graph G has an equitable tree- k -coloring for any integer k ≥ ⌈ (Δ (G) + 1) / 2 ⌉ , solving a conjecture of Wu, Zhang and Li (2013) for interval graphs, and furthermore, give a linear-time algorithm for determining whether a proper interval graph admits an equitable tree- k -coloring for a given integer k. For disjoint union of split graphs, or K 1 , r -free interval graphs with r ≥ 4 , we prove that it is W 1 -hard to decide whether there is an equitable tree- k -coloring when parameterized by number of colors, or by treewidth, number of colors and maximum degree, respectively. On the positive side, we propose a quadratic 2-approximation algorithm for the equitable tree-coloring problem in chordal graphs. Moreover, it is proved that there is no α -approximation algorithm for any α < 3 2. [ABSTRACT FROM AUTHOR]

The general position-dependent scheduling problems are studied in this paper. A 2-approximation algorithm is proposed for the learning scheduling problem on a single machine with release time to minimize the makespan. To minimize the total completion time on a single machine with release time and learning effect, we design a 2-approximation algorithm and a P T A S. Moreover, for the deteriorating scheduling problem to minimize the makespan on parallel machines, a 2-approximation algorithm is provided. [ABSTRACT FROM AUTHOR]

Unmanned Aerial Vehicles (UAVs) are expected to be important components in the upcoming wireless communication field, which are increasingly used as data collectors to gather sensory data from Wireless Sensor Networks (WSNs) due to their high mobility, flexible deployment. Since the storage capacity and lifetime of sensors are increasing with the development of science and technology, sensors can store more and more sensing data about the monitoring area. However, due to the energy limitation of UAVs and a large amount of data carried by sensors, we can not collect all data from WSN within the limited time. Therefore, in this paper, we investigate two problems: (1) without the energy limitation of UAV, how to optimize the trajectory of UAV to minimize the sum of traveling time and data transmission time of UAV while guaranteeing the amount of data collected from each sensor reaches to a certain proportion of the original data, which is called the Minimizing Transportation and Communication Latency (MTCL) problem; (2) given the limited budget of UAV, how to find the optimal trajectory of UAV to maximize the minimum ratio of the collected data to the stored data among all sensors, which is called the Maximizing Data Collection Proportion (MDCP) problem. We first prove that both the problems are NP-Complete. Then we study a special case of the MTCL problem, which is called the MTCL-disjoint problem, in which any pair of data collection areas are disjoint, and we propose an approximation algorithm to solve the MTCL-disjoint problem. Based on the MTCL-disjoint problem, we propose an approximation algorithm for the general MTCL problem. Afterward, an approximation algorithm for the MDCP problem is proposed on the basis of the algorithm for the MTCL problem. Finally, we present numerical results in different scenarios to assess the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]