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]

Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for flows in large networks. In this study, we focus on a problem, called the single allocation hub-and-spoke network design problem. In the problem, the goal is to allocate each non-hub node to exactly one of the given hub nodes so as to minimize the total transportation cost. The problem is essentially equivalent to another combinatorial optimization problem, called the metric labeling problem. The metric labeling problem was first introduced by Kleinberg and Tardos in 2002, motivated by application to segmentation problems in computer vision and related areas. In this study, we deal with a case where the set of hubs forms a star, which is encountered especially in telecommunication networks. We propose a polynomial-time randomized approximation algorithm for the problem, whose approximation ratio is less than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding procedures. [ABSTRACT FROM AUTHOR]

We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from either an edge- or a vertex-colored, color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, and then, we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids. [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]

A Roman dominating function (RDF) of a graph G = (V , E) is a function f : V → { 0 , 1 , 2 } such that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. A global Roman dominating function (GRDF) of a graph G = (V , E) is a function f : V → { 0 , 1 , 2 } such that f is a Roman dominating function of both G and its complement G ¯. The weight of f is f (V) = Σ u ∈ V f (u). The minimum weight of a GRDF in a graph G is known as global Roman domination number of G and is denoted by γ g R (G). Minimum Global Roman Domination is to find a global Roman dominating function of minimum weight and Decide Global Roman Domination is the decision version of Minimum Global Roman Domination. In this paper, we show that Decide Global Roman Domination is NP -complete for bipartite graphs and chordal graphs. On the positive side, we give a polynomial-time algorithm for Minimum Global Roman Domination for threshold graphs. Further, we propose an O (ln | V |) -approximation algorithm for Minimum Global Roman Domination for a graph G = (V , E). We also show that Minimum Global Roman Domination cannot be approximated within a factor of (1 − ϵ) ln | V | for any ϵ > 0 unless P = NP. Next, we show that Minimum Global Roman Domination admits a constant approximation algorithm for bounded degree graphs. Finally, we show that Minimum Global Roman Domination is APX -complete for bounded degree graphs. [ABSTRACT FROM AUTHOR]

For a connected graph G = (V , E) , a function r i : V ↦ { 0 , 1 , 2 } is an Italian dominating function (IDF) if every vertex v with r i (v) = 0 is either adjacent to a vertex u with r i (u) = 2 or adjacent to at least two vertices x , y with r i (x) = r i (y) = 1. The weight of r i is ∑ v ∈ V r i (v) and the minimum Italian dominating function problem (MinIDF) is to compute an IDF with minimum weight. The minimum connected Italian dominating function problem (MinCIDF) is to find a minimum weight IDF r c i such that the subgraph of G induced by vertex set { v ∈ V ∣ r c i (v) = 1 or r c i (v) = 2 } is connected. In this paper, we give a greedy algorithm for the MinIDF problem with approximation ratio at most 2 + ln (1 2 Δ + 1) , and a greedy algorithm for the MinCIDF problem with approximation ratio at most 4 + ln (1 2 Δ − 1) , where Δ is the maximum degree of the graph. [ABSTRACT FROM AUTHOR]

The length of a tree-decomposition of a graph is the maximum distance (in the graph) between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3 2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the size of a largest isometric cycle. This work initiates the study of treelength in planar graphs by considering the next natural subclass of planar graphs, namely the one of series–parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3 2 in series–parallel graphs. Our main result is a quadratic-time algorithm for deciding whether a series–parallel graph has treelength at most 2. Our latter result relies on a characterization of series–parallel graphs with treelength 2 in terms of an infinite family of forbidden isometric subgraphs. [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]

In the multiway cut problem we are given a weighted undirected graph G = (V , E) and a set T ⊆ V of k terminals. The goal is to find a minimum weight set of edges E ′ ⊆ E with the property that by removing E ′ from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio 2 − 2 k . We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem. [ABSTRACT FROM AUTHOR]

The problem of k orthogonal line center is about computing a set of k axis-parallel lines for a given set of points in ℜ 2 such that the maximum among the distances between each point to its nearest line is minimized. A 2-factor approximation algorithm and a (5 3 , 3 2) bi-criteria approximation algorithm is presented for the problem. Both of them are deterministic approximation algorithms using combinatorial techniques and having sub-quadratic running times. [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]

Broadcasting in a computer network is a method of transferring a message to all recipients simultaneously. It is common in this situation to use a tree with many leaves to perform the broadcast, as internal nodes have to forward the messages received, while leaves are only receptors. We consider the subjacent problem of, given a directed graph D , finding a spanning arborescence of D , if one exists, with the maximum number of leaves. In this paper, we concentrate on the class of rooted directed acyclic graphs, for which the problem is known to be MaxSNP-hard. A 2-approximation was previously known for this problem on this class of directed graphs. We improve on this result, presenting a 3 2 -approximation. We also adapt a result for the undirected case and derive an inapproximability result for the vertex-weighted version of Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs. [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]

Let G (V , E , c , w) be a weighted graph with vertex set V , edge set E , vertex-capacity function c : V → R + , and edge-weight function w : E → R + . In Bumblebee visitation problem , a mobile agent Bumblebee, denoted by B , begins by entering a vertex of the graph, and then moves along the edges of the graph. When B moves along an edge e = u v , both c (u) and c (v) are decreased by w (e). The Bumblebee visitation problem deals with placing and moving B in G such that the sum of the residual-capacities at the visited vertices is maximum. We consider four variants of this problem depending on edge-weights and constraints on the possible movements of B. The four variants are uniform-weight-constrained Bumblebee Visitation problem , variable-weight-constrained Bumblebee Visitation problem , uniform-weight-unconstrained Bumblebee Visitation problem , and variable-weight-unconstrained Bumblebee Visitation problem. We show that all four variants are NP-hard for general graphs, and the variable-weight constrained variant is NP-hard even for star graphs (K 1 , n). On the positive side, for the uniform-weight constrained variant, we give a dynamic programming based linear-time algorithm for trees and a quadratic-time algorithm for cactus. We then extend these algorithms for the variable-weight unconstrained variant. We also give a 3-factor approximation algorithm for the uniform-weight unconstrained variant where each vertex-capacity is at least five. [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]

Temporal graphs are graphs where the topology and/or other properties of the graph change with time. They have been used to model applications with temporal information in various domains. Problems on static graphs become more challenging to solve in temporal graphs because of dynamically changing topology, and many recent works have explored graph problems on temporal graphs. In this paper, we define a type of matching called 0-1 timed matching for temporal graphs, and investigate the problem of finding a maximum 0-1 timed matching for different classes of temporal graphs. We assume that only the edge set of the temporal graph changes with time. Thus, a temporal graph can be represented by associating each edge with one or more non-overlapping discrete time intervals for which that edge exists. We first prove that the problem is NP-complete for rooted temporal trees when each edge is associated with two or more time intervals. We then propose an O (n log n) time algorithm for the problem on a rooted temporal tree with n vertices when each edge is associated with exactly one time interval. The problem is then shown to be NP-complete also for bipartite temporal graphs even when each edge is associated with a single time interval and degree of each vertex is bounded by a constant k ≥ 3. We next investigate approximation algorithms for the problem for temporal graphs where each edge is associated with more than one time intervals. It is first shown that there is no 1 n 1 − ϵ -factor approximation algorithm for the problem for any ϵ > 0 even on a rooted temporal tree with n vertices unless NP = ZPP. We then present a 5 2 N ∗ + 3 -factor approximation algorithm for the problem for general temporal graphs where N ∗ is the average number of edges overlapping in time with each edge in the temporal graph. The same algorithm is also a constant-factor approximation algorithm for temporal graphs with degree of each vertex bounded by a constant. [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]

We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O (n m 2) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n (m) is the number of variables (clauses). As a by-product, we obtain a 2 (1 − 1 / 2 k) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. [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]

We introduce a new graph-theoretic concept in the area of network monitoring. A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e of G , there are a vertex x of M and a vertex y of G such that e belongs to all shortest paths between x and y. We denote by dem (G) the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G ; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge. In this paper, we initiate the study of this new concept. We show that for a nontrivial connected graph G of order n , 1 ≤ dem (G) ≤ n − 1 with dem (G) = 1 if and only if G is a tree, and dem (G) = n − 1 if and only if it is a complete graph. We compute the exact value of dem for grids, hypercubes, and complete bipartite graphs. Then, we relate dem to other standard graph parameters. We show that dem (G) is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. It is also upper-bounded by twice its feedback edge set number. Moreover, we characterize connected graphs G with dem (G) = 2. Then, we show that determining dem (G) for an input graph G is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikely to be fixed parameter tractable when parameterized by the solution size. [ABSTRACT FROM AUTHOR]

Given a graph G , we call a partition (V 1 , V 2 , ... , V k) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k ≥ 3 and has a polynomial time algorithm for each k ≤ 2. (2) It is NP-hard to approximate the minimum induced star partition size within n 1 2 − ϵ for all ϵ > 0. (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K 1 , r -free graphs, r ≥ 3), K 1 , 5 -free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r 2 -approximation algorithm for K 1 , r -free graphs (r ≥ 2) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature. [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]

A subset D ⊆ V of a graph G = (V , E) is called a global total k -dominating set of G if D is a total k -dominating set of both G and G ¯ , the complement of G. The Minimum Global Total k - Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and the Decide Global Total k - Domination problem is the decision version of the Minimum Global Total k - Domination problem. The Decide Global Total k - Domination problem is known to be NP -complete for general graphs. In this paper, we study the complexity of the Minimum Global Total k - Domination problem. We show the Decide Global Total k - Domination problem remains NP -complete for bipartite graphs and chordal graphs. We also show that Minimum Global Total k - Domination cannot be approximated within a factor of (1 − ϵ) ln | V | for any ϵ > 0 unless P = NP for bipartite graphs as well as for chordal graphs. Next, we show that Minimum Global Total k - Domination admits a constant approximation algorithm for bounded degree graphs. Finally, we show that Minimum Global Total k - Domination problem is APX -complete for bounded degree graphs. We also show that Decide Global Total k - Domination problem is W[2] -hard for bipartite graphs and for chordal graphs when we choose the size of the GTkD-set as the parameter. [ABSTRACT FROM AUTHOR]

We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least Δ jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic. [ABSTRACT FROM AUTHOR]

We consider single machine scheduling problems with additional non-renewable resource constraints. Examples for non-renewable resources include raw materials, energy, or money. Usually they have an initial stock and replenishments arrive over time at a-priori known time points and quantities. The jobs have some requirements from the resources and a job can only be started if the available quantity from each of the required resources exceeds the requirements of the job. Upon starting a job, it consumes its requirements which decreases the available quantities of the respective non-renewable resources. There is a broad background for this class of problems. Most of the literature concentrate on the makespan, and the maximum lateness objectives. This paper focuses on the total weighted completion time objective for which the list of the approximation algorithms is very short. We extend that list by considering new special cases and obtain new complexity results and approximation algorithms. [ABSTRACT FROM AUTHOR]

We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O (log n) -approximation algorithm, based on the submodular goal-value approach of Deshpande, Hellerstein and Kletenik. Our second algorithm, which is simple, is based on the algorithm solving the SBFE problem for k -of- n functions, due to Salloum, Breuer, and Ben-Dov. It achieves a (B − 1) approximation factor, where B is the number of blocks of 0's and 1's in the standard vector representation of the symmetric Boolean function. As part of the design of the first algorithm, we prove that the goal value of any symmetric Boolean function is less than n (n + 1) / 2. Finally, we give an example showing that for symmetric Boolean functions, minimum expected verification cost and minimum expected evaluation cost are not necessarily equal. This contrasts with a previous result, given by Das, Jafarpour, Orlitsky, Pan and Suresh, which showed that equality holds in the unit-cost case. [ABSTRACT FROM AUTHOR]

We study the Student-Project Allocation problem with lecturer preferences over Projects (spa-p). In this context it is known that stable matchings can have different sizes and the problem of finding a maximum size stable matching is NP-hard. There are two known approximation algorithms for max-spa-p , with performance guarantees 2 and 3 2. We show that max-spa-p is polynomial-time solvable if there is only one lecturer involved, and NP-hard to approximate within some constant c > 1 if there are two lecturers involved. We also show that this problem remains NP-hard if each preference list is of length at most 3, with an arbitrary number of lecturers. We then describe an Integer Programming (IP) model to enable max-spa-p to be solved optimally in the general case. Following this, we present results arising from an empirical evaluation that investigates how the solutions produced by the approximation algorithms compare to optimal solutions obtained from the IP model, with respect to the size of the stable matchings constructed, on instances that are both randomly-generated and derived from real datasets. [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]

We present a (1 + k k + 2) -approximation algorithm for the Maximum k - dependent Set problem on bipartite graphs for any k ≥ 1. For a graph with n vertices and m edges, the algorithm runs in O (k m n) time and improves upon the previously best-known approximation ratio of 1 + k k + 1 established by Kumar et al. (2014). Our proof also indicates that the algorithm retains its approximation ratio when applied to the (more general) class of König–Egerváry graphs. [ABSTRACT FROM AUTHOR]

Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an edge-weighted undirected graph G = (V , E , w) , we are asked to find S ⊆ V that maximizes the density d (S) , i.e., half the weighted average degree of the induced subgraph G [ S ]. This problem can be solved exactly in polynomial time and well-approximately in almost linear time. However, a densest subgraph has a structural drawback, namely, the subgraph may not be robust to vertex/edge failure. Indeed, a densest subgraph may not be well-connected, which implies that the subgraph may be disconnected by removing only a few vertices/edges within it. In this paper, we provide an algorithmic framework to find a dense subgraph that is well-connected in terms of vertex/edge connectivity. Specifically, we introduce the following problems: given a graph G = (V , E , w) and a positive integer/real k , we are asked to find S ⊆ V that maximizes the density d (S) under the constraint that G [ S ] is k -vertex/edge-connected. For both problems, we propose polynomial-time (bicriteria and ordinary) approximation algorithms, using classic Mader's theorem in graph theory and its extensions. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph on n vertices, where d (v) denotes the degree of vertex v , and t (v) is a threshold associated with v. We consider a process in which initially a set S of vertices becomes active, and thereafter, in discrete time steps, every vertex v that has at least t (v) active neighbors becomes active as well. The set S is contagious if eventually all V becomes active. The target set selection problem TSS asks for the smallest contagious set. TSS is NP-hard and moreover, notoriously difficult to approximate. In the conservative special case of TSS, t (v) > 1 2 d (v) for every v ∈ V. In this special case, TSS can be approximated within a ratio of O (Δ) , where Δ = max v ∈ V [ d (v) ]. In this work we introduce a more general class of TSS instances that we refer to as conservative on average (CoA), that satisfy the condition ∑ v ∈ V t (v) > 1 2 ∑ v ∈ V d (v). We design approximation algorithms for some subclasses of CoA. For example, if t (v) ≥ 1 2 d (v) for every v ∈ V , we can find in polynomial time a contagious set of size O ̃ Δ ⋅ O P T 2 , where O P T is the size of a smallest contagious set in G. We also provide several hardness of approximation results. For example, assuming the unique games conjecture, we prove that TSS on CoA instances with Δ ≤ 3 cannot be approximated within any constant factor. We also present results concerning the fixed parameter tractability of CoA TSS instances. [ABSTRACT FROM AUTHOR]

In this paper, we consider the following variations of the Line Segment Disk Cover (LSDC) problem. LSDC-H : In this version of LSDC problem, we are given a set S = { s 1 , s 2 , ... , s n } of n horizontal line segments of arbitrary length and an integer k (≥ 1). Our aim is to cover all segments in S with k disks of minimum radius centered at arbitrary points in the plane. LSDC-A : In this version of LSDC problem, we are given a set S = { s 1 , s 2 , ... , s n } of n line segments of arbitrary length with arbitrary orientation and an integer k (≥ 1). Our aim is to cover all segments in S with k disks of minimum radius centered at arbitrary points in the plane. LSDC-D : In the discrete version of LSDC problem, we are given a set S = { s 1 , s 2 , ... , s n } of n line segments of arbitrary length with arbitrary orientation and a set D = { d 1 , d 2 , ... , d m } of m disks of unit radius. Our aim is to cover all segments in S with the minimum number of disks in D i.e., find D ′ such that S ⊂ ⋃ d ∈ D ′ d , where D ′ ⊆ D is of minimum cardinality. For LSDC-H and LSDC-A problems, we propose (1 + ε) -factor approximation algorithms, which run in O ( (max { 4 δ − 2 , 1 }) k n (| log r o p t | + log ⌈ 1 ρ ⌉)) time and O ( (max { 4 δ − 2 , 1 }) k n log n (| log r o p t | + log ⌈ 1 ρ ⌉)) time, respectively, where r o p t is the minimum radius of k disks which cover all segments in S , and δ > 0 , ρ > 0 and ε > 0 are fixed constants such that ε ≥ (δ + δ ρ + ρ). For LSDC-D problem, we propose a (1 + ε) -factor approximation algorithm (PTAS), which runs in O (m 2 (8 2 ε) 2 + 3 + m 2 n) time, where 0 < ε ≤ 2 , and a (9 + ε) -factor approximation algorithm, which runs in O (m (5 + 18 ε) log m + m 2 n) time, where 0 < ε ≤ 6. For LSDC-D problem, we also have developed a faster approximation algorithm based on a simple greedy strategy. The running time and the approximation factor of the greedy algorithm are O (k (m n + m log m)) and δ 1 δ k , respectively, where k is the output size, and δ 1 and δ k are the largest sums of lengths of parts of line segments that lie within a disk in the first and the last (k t h) iteration of the greedy algorithm, respectively. [ABSTRACT FROM AUTHOR]

We present a low-constant approximation for the metric k -median problem on insertion-only streams using O (ε − 3 k log n) space. In particular, we present a streaming (O (ε − 3 k log n) , 2 + ε) -bicriterion solution that reports cluster weights. Running the offline approximation algorithm due to Byrka et al. (2015) on this bicriterion solution yields a (17. 66 + ε) -approximation (Guha et al., 2003; Charikar et al., 2003; Braverman et al., 2011). Our result matches the best-known space requirements for streaming k -median clustering while significantly improving the approximation accuracy. We also provide a lower bound, showing that any polylog (n) -space streaming algorithm that maintains an (α , β) -bicriterion must have β ≥ 2. Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By storing an accurate summary of recent segments of the stream and a lower-space summary of older segments, our algorithm maintains a (O (ε − 3 k log n) , 2 + ε) -bicriterion solution for the entirety of the stream. In addition to our main result, we introduce a novel construction that we call a candidate set. This is a collection of points that, with high probability, contains k points that yield a near-optimal k -median cost. We present an algorithm called monotone faraway sampling (MFS) for constructing a candidate set in a single pass over a data stream. We show that using this candidate set in tandem with a coreset speeds up the search for a solution set of k cluster centers upon termination of the data stream. While coresets of smaller asymptotic size are known, comparative simplicity of MFS makes it appealing as a practical technique. [ABSTRACT FROM AUTHOR]

We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of subset selection problems with linear constraints. Given a problem in this class and some small ε ∈ (0 , 1) , we show that if there exists an r -approximation algorithm for the Lagrangian relaxation of the problem, for some r ∈ (0 , 1) , then our technique achieves a ratio of r r + 1 − ε to the optimal, and this ratio is tight. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the maximum generalized assignment problem (GAP) and maximum weight independent set. For all of the problems studied in this paper, the number of calls to the r -approximation algorithm, used by our algorithms, is linear in the input size and in log (1 ∕ ε) for inputs with a cardinality constraint, and polynomial in the input size and in log (1 ∕ ε) for inputs with an arbitrary linear constraint. [ABSTRACT FROM AUTHOR]

We study robust solutions for combinatorial optimization problems with budgeted uncertainty sets in the min–max–min setting, where the decision maker is allowed to choose a set of k different solutions from which one can be chosen after the uncertain scenario has been revealed. We first show how the problem can be decomposed into polynomially many subproblems if k is fixed. We then consider the special case where k = 2 , i.e., one is allowed to choose two different solutions to hedge against the uncertainty. Using the decomposition, we provide polynomial-time algorithms for the unconstrained combinatorial optimization problem, the matroid maximization problem, the selection problem, and the shortest path problem on series–parallel graphs. The shortest path problem on general graphs turns out to be NP -hard. We show how to transform approximation algorithms for minimization subproblems to approximation algorithms for the robust problem and study the knapsack problem to show that this does not hold for maximization problems in general. We present a PTAS for the corresponding subproblem and prove that the min–max–min knapsack problem with k = 2 is not approximable at all. [ABSTRACT FROM AUTHOR]

We are given a graph G = (V ∪ T , E) , with V ∪ T the set of vertices where T is a set of terminals and E the set of edges. The multi-terminal vertex separator problem consists in finding a subset of vertices S ⊆ V of minimum size intersecting all paths between every pair of terminals. In this paper we present three extended linear integer programming formulations for the multi-terminal vertex separator problem and we develop Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present the pricing problem, the branching scheme and the computation of the dual bound used during the column generation phase. Computational results are reported comparing the performance of the formulations on a set of instances. [ABSTRACT FROM AUTHOR]

Submodular maximization is well studied in the fields of data mining and machine learning. We study the submodular maximization subject to a cardinality constraint k for large scale scenarios applications under two combined settings. One is that all elements arrive in a streaming fashion, and the other is that some elements may be invalid at last. For this problem, which is called streaming robust submodular maximization (SRSM) problem, we explore an approximation algorithm, returning a subset S from the ground set V with a limit size, such that it represents V and is robust to a broken set E well. Our algorithm only makes one pass over data, and achieves a constant-factor 0.1224 approximation guarantee, independent of the cardinality constraint parameter k. Based on the algorithm for SRSM problem, we continue to discuss this problem over sliding windows, in which we are asked to obtain a proper set that only considers the last W elements, and derive an algorithm with a constant (0. 0612 − ϵ) -approximation guarantee. At last we also propose numerical experiments on some applications to well demonstrate our algorithm for SRSM problem over sliding windows. [ABSTRACT FROM AUTHOR]

We consider the dispersed p → -neighbor k -supplier problem. In the classical k -supplier problem, we have to select k suppliers in a metric space such that the maximum distance between a customer and its closest supplier is minimized. Here, we generalize this problem to the case where each customer possibly needs service from more than one supplier. Moreover, the selected suppliers should not be too close to each other, i.e., they need to be dispersed. For the classical k -supplier problem, and its special case the k -center problem, there is a 3- and a 2-approximation respectively. We show that these guarantees can also be given in the case when customers need service from multiple suppliers, without imposing dispersion constraints. If we generalize the problem to the dispersed case, without imposing neighboring constraints, we get inapproximability results depending on the measure of dispersion. We also show (almost) matching upper bounds. Finally, we show that adding both the neighbor requirement and the dispersion requirement leads to an inapproximable problem. [ABSTRACT FROM AUTHOR]

In the Multi-Spreader Crane Scheduling Problem (MSCSP), containers with identical dimensions but variable weights are arranged along a grid. A multi-spreader crane is used to lift all the containers. The crane has m > 1 modes. When it is in the p th mode, the crane can remove p adjacent containers along the same row at the same time as long as the total weight of the containers does not exceed the loading capacity κ p. Such a lift takes h p minutes. It also takes c p , q minutes for the crane to switch from mode p to q when p ≠ q. The goal is to find a crane lift sequence so that the total time it takes to lift all the containers is minimized. This paper investigates the computational complexity of MSCSP. First, we establish a connection between greedy crane lift sequences and supersequences. We then prove that MSCSP is NP-hard when the crane has three or more modes by a reduction from a version of the Shortest Common Supersequence problem. Lastly, we investigate two problems that arise naturally when heuristics are used to solve MSCSP. We show that one can be solved using dynamic programming while the other remains computationally hard. We also provide an approximation algorithm that behaves nicely when the changeover times are not much larger than the lifting times of the crane. [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]

We study the problem of decomposing a graph into stars so that the minimum size star in the decomposition is as large as possible. Problems of graph decomposition have been actively investigated since the 70's. The question we consider here also combines the structure of a facility location problem (choosing the centres of the stars) with a max–min fairness optimization criterion that has recently received attention in resource allocation problems, e.g., the Santa Claus problem. We focus on computational and algorithmic questions: We show that the problem is hard even in the case of planar graphs of maximum degree not larger than four, and already for decompositions into stars of size at least three. We are able to tightly characterize the boundaries between efficiently solvable instances and hard ones: we show that relaxing any of the conditions in our hardness result (minimum size of the stars or degree of the input graph) makes the problem polynomially solvable. Our complexity result implies also the APX hardness of the problem ruling out any approximation guarantee better than 2/3. We complement this inapproximability result with a 1/2-approximation algorithm. Finally, we give a polynomial time algorithm for trees. A nice property of our algorithms is that they can all be implemented to run in time linear in the size of the input graph. [ABSTRACT FROM AUTHOR]

The positive influence dominating set(PIDS) problem is a well-known APX-hard problem and there exists a greedy approximation algorithm with an approximation ratio of H (δ). However, the PIDS which is formed by this algorithm is not connected. This paper proposes an algorithm with an approximation ratio of H (12) to find the connected PIDS in a cubic graph. Furthermore, this paper also proposes an algorithm with an approximation ratio of H (9) to find the partial positive influence dominating set(PPIDS). Both of these two algorithms have a time complexity of O (n 3). In addition, we prove that for every node in the PIDS(or PPIDS) which is formed by our algorithms, there exists at least one node in the PIDS(or PPIDS) that is its two-hop neighbor. We also proved that in a cubic graph, the subgraph induced by PIDS is connected. These conclusions are also true in k-regular graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider Euclidean versions of the 2-tuple dominating set problem and the liar's dominating set problem. For a given set P = { p 1 , p 2 , ... , p n } of n points in R 2 , the objective of the Euclidean 2-tuple dominating set problem is to find a minimum size set D ⊆ P such that | N p i ∩ D | ≥ 2 for each p i ∈ P , where N p i = { p j ∈ P ∣ δ (p i , p j) ≤ 1 } and δ (p i , p j) is the Euclidean distance between p i and p j. The objective of the Euclidean liar's dominating set problem is to find a set D (⊆ P) of minimum size satisfying the following two conditions: (i) D is a 2-tuple dominating set of P , and (ii) for every distinct pair of points p i and p j in P , | (N p i ∪ N p j ) ∩ D | ≥ 3. We first propose a simple O (n log n) time 63 2 -factor approximation algorithm for the Euclidean liar's dominating set problem. Next, we propose approximation algorithms to improve the approximation factor to 732 α for 3 ≤ α ≤ 183 , and 846 α for 3 ≤ α ≤ 282. The running time of both the algorithms is O (n α + 1 Δ) , where Δ = max { | N p | : p ∈ P }. Finally, we propose a PTAS for the Euclidean 2-tuple dominating set problem. [ABSTRACT FROM AUTHOR]

Line of Sight (LoS) networks provide a model of wireless communication which incorporates visibility constraints. Vertices of such networks can be embedded onto the cube { (x 1 , x 2 , ... , x d) : x i ∈ { 1 , ... , n } , 1 ≤ i ≤ d } so that two vertices are adjacent if and only if their images lay on a line parallel to one of the cube edges and their distance is less than a given range parameter ω. In this paper we study large independent sets in LoS networks. We prove that the computational problem of finding a maximum independent set can be solved optimally in polynomial time for one dimensional LoS networks. However, for d ≥ 2 , the (decision version of) the problem becomes NP-complete for any fixed ω ≥ 3. In addition, we show that the problem is APX-hard when ω = n for d ≥ 3. On the positive side, we show that LoS networks generalize chordal graphs. This implies that there exists a simple d -approximation algorithm for the maximum independent set problem in LoS networks. Finally, we describe a polynomial time approximation scheme for the maximum independent set problem in LoS networks for the case when ω is a constant and present an improved heuristic algorithm for the problem in the case ω = n. [ABSTRACT FROM AUTHOR]

We consider several problems dealing with tracking of moving objects (e.g., vehicles) in networks. Given a graph G = (V , E) and two vertices s , t ∈ V , a set of vertices T ⊆ V is a tracking set for G (w.r.t. paths from s to t), if one can distinguish between any two paths from s to t by the order in which the vertices of T appear (or do not appear) in them. We prove that the problem of finding a minimum-cardinality tracking set w.r.t. shortest paths from s to t is NP-hard and even APX-hard. On the other hand, for the common case where G is planar, we present a 2-approximation algorithm for this problem. We also describe how to preprocess G (and its tracking set w.r.t. shortest paths from s to t), so that given a sequence of visited trackers, one can reconstruct the traversed path P in O (| P |) time. Moreover, we consider the following related problem: Given a graph G , two vertices s and t , and a set of forbidden vertices F ⊆ V − { s , t } , find a minimum-cardinality set of trackers V ∗ ⊂ V , such that a shortest path P from s to t passes through a forbidden vertex if and only if it passes through a vertex of V ∗. We present a polynomial-time (exact) algorithm for this problem. [ABSTRACT FROM AUTHOR]

For a graph G and a non-negative integral weight function w on the vertex set of G , a set S of vertices of G is w -safe if w (C) ≥ w (D) for every component C of the subgraph of G induced by S and every component D of the subgraph of G induced by the complement of S such that some vertex in C is adjacent to some vertex of D. The minimum weight w (S) of a w -safe set S is the safe number s (G , w) of the weighted graph (G , w) , and the minimum weight of a w -safe set that induces a connected subgraph of G is its connected safe number c s (G , w). Bapat et al. showed that computing c s (G , w) is NP-hard even when G is a star. For a given weighted tree (T , w) , they described a polynomial time 2-approximation algorithm for c s (T , w) as well as a polynomial time 4-approximation algorithm for s (T , w). Addressing a problem they posed, we present a PTAS for the connected safe number of a weighted tree. Our PTAS partly relies on an exact pseudopolynomial time algorithm, which also allows to derive an asymptotic FPTAS for restricted instances. Finally, we extend a bound due to Fujita et al. from trees to block graphs. [ABSTRACT FROM AUTHOR]

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS'05), in which we are given a demand r t ∈ { 0 , 1 } for instant of time t = 0 , ... , T − 1 , along with K permit types with lengths of time δ 1 , ... , δ K and sub-additive costs. A permit is a pair (k , t ˆ) ∈ K × Z + , and it covers interval t ˆ , t ˆ + δ k). We wish to find a minimum-cost set of permits that covers every t with r t = 1. Meyerson gave deterministic O (K) -competitive and randomized O (lg K) -competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant ( r t ∈ Z + ) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O (K) -competitive online algorithm and a randomized O (lg K) -competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O (lg n) -approximation algorithm and a O (lg K lg | V |) -competitive online algorithm, where n is the number of requests and | V | is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γ k and covering one demand per instant of time, or a group permit, which costs M ⋅ γ k for some constant M ≥ 1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O (K) -competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O (K) -competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard. [ABSTRACT FROM AUTHOR]

We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing polynomial-time approximation schemes motivated the development of faster constant approximation algorithms. In this paper, we present a 2.16-approximation algorithm that runs in O (n log 2 n) time and a 2-approximation algorithm that runs in O (n 2 log n) time for the unweighted version of the problem. In the weighted version, the running times increase by an O (log n) factor. Our algorithms are based on a classic strip decomposition, but we improve over previous algorithms by efficiently using geometric data structures. We also propose a PTAS for the unweighted version. [ABSTRACT FROM AUTHOR]