Search

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]

In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max { 1 + 1. 5 α , 3 } and 6, respectively, where α is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees. These results extend the results in Anupam Gupta et al. (2012) and Daya Ram Gaur et al. (2013). The bounds reported here improve the bounds in Daya Ram Gaur et al. (2016). [ABSTRACT FROM AUTHOR]

This paper presents a lower bound on the running time of any approximation scheme for Minimum Color-Spanning Ball (MCSB) problem in high dimensional spaces. This bound is based on the Exponential Time Hypothesis (ETH). [ABSTRACT FROM AUTHOR]

The partial covering 0–1 integer program (PCIP) is a relaxed problem of the covering 0–1 integer program (CIP) such that some fixed number of constraints may not be satisfied. This type of relaxation is also discussed in the partial set multi-cover problem (PSMCP) and the partial set cover problem (PSCP). In this paper, we propose an approximation algorithm for PCIP by extending an approximation algorithm for PSCP by Gandhi et al. (2004). [ABSTRACT FROM AUTHOR]

Finding actionable patterns from massive data is a crucial task in data mining applications. In Formal Concept Analysis (FCA), concept stability is one of the commonly used measures for assessing the interestingness of formal concepts, and hence selecting the relevant patterns of such a type. Accurate and scalable computation of concept stability often remains a key challenge. While exact methods for computing stability can be an effective solution in small applications, their algorithmic complexity is however at least quadratic in the size of the input lattice which could be exponential with respect to the size of the context. As such, approximation algorithms like Monte Carlo Sampling (MCS) have been applied to be more effective in practice. However, MCS often has a slow convergence problem with an inaccurate estimation of stability. In this paper, we introduce a new set of approximation methods to estimate the stability index based on variance reduction techniques. Specifically, we focus on adapting Latin hypercube (LHS), scrambled Sobol (SoS) and Latin supercube (LSS) sampling methods to exploit the potential of stratification and Low-discrepancy as well as hybridization approaches to improve the convergence rate. In contrast to the pure randomness of MCS, the proposed methods aim to spread the sample points more evenly across all possible subsets of concept intent (or extent). This allows all the areas of the intent powerset space to be properly represented. Our experiments on several formal contexts illustrate the efficiency of LHS, SoS and LSS over MCS. [ABSTRACT FROM AUTHOR]

We study the allocation problem of a compound request for a service chain in a software defined network that supports network function virtualization. Given a network that contains servers with limited processing power and links with limited bandwidth, a service chain is a sequence of virtual network functions (VNFs) that serve a certain flow request in the network. The allocation of a service chain consists of routing and VNF placement, namely each VNF from the sequence is placed in a server along a path. It is feasible if each server can handle the VNFs that are assigned to it, and if each link on the path can carry the flow that is assigned to it. A request for service is composed of a source and a destination in the network, an upper bound on the total latency, and a specification in the form of a directed acyclic graph (DAG) of VNFs that provides all service chains that are considered valid for this request. In addition, each pair of server and VNF is associated with a cost for placing the VNF in the server. Given a request, the goal is to find a valid service chain of minimum total cost that respects the latency constraint or to identify that such a service chain does not exist. We show that even the feasibility problem is NP-hard in general graphs. Hence we focus on DAGs. We show that the problem is still NP-hard in DAGs even for a very simple network, and even if the VNF specification consists of only one option (i.e., the virtual DAG is a path). On the other hand, we present an FPTAS for the case where the network is a DAG. In addition, based on our FPTAS, we provide algorithms for general instances in which the service chain passes through a bounded number of vertices whose degree is larger than two. Finally, we provide an FPTAS for a fault-tolerant version of the problem. [ABSTRACT FROM AUTHOR]

A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein (2001) and studied in a number of articles. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs, namely those excluding a C 4 or with maximum degree at most three. In particular, we achieve a ratio of 5 ∕ 9 for subcubic bipartite graphs, improving over a 1 ∕ 2 -approximation algorithm proposed by Mishra (2011). [ABSTRACT FROM AUTHOR]

We study the fault-tolerant facility location problem with penalties (FTFLPWP). We present an LP-rounding 4-approximation algorithm. Then we apply the randomized rounding technique to improve the approximation to 3.16, which is further improved to 2.408 by the greedy augmentation technique. [ABSTRACT FROM AUTHOR]

Facility location problem is one of the most classical NP-hard problems in combinatorial optimization. In the metric facility location problem (MFLP), we are given a set of facilities, a set of clients and the metric distances between facilities and clients. In this paper, we consider the squared metric facility location problem (SMFLP) with nonuniform capacities, where each facility has a nonuniform capacity to serve a limited amount of client demands, and the distances between facilities and clients are no longer metric but squared metric. Fernandes et al. (2015) analyze the LP-based algorithms for the MFLP when they are applied to the SMFLP and achieve constant approximation ratios. In this paper, we do the same thing on local search algorithm, one of the most powerful techniques for MFLP with nonuniform capacities. Particularly, we propose the first constant approximation algorithm with approximation ratio 13 + ϵ for the SMFLP with nonuniform capacities. [ABSTRACT FROM AUTHOR]

We consider the 0–1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The contribution of a packed item in each time period depends on its profit as well as on a time factor which reflects the importance of the period in the objective function. The problem calls for maximizing the weighted sum of the profits over the whole time horizon. In this work, we provide approximation results for IKP and its restricted variants. In some results, we rely on Linear Programming (LP) to derive approximation bounds and show how the proposed LP-based analysis can be seen as a valid alternative to more formal proof systems. We first manage to prove the tightness of some approximation ratios of a general purpose algorithm currently available in the literature and originally applied to a time-invariant version of the problem. We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating the number of periods is considered as a constant. Then, we add the mild and natural assumption that each item can be packed in the first time period. For this variant, we discuss different approximation algorithms suited for any number of time periods and for the special case with two periods. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling independent jobs with a common due date on a single machine with the objective of maximizing the number of early jobs. The processing times are uncertain and take any value from a certain job dependent interval. For measuring the quality of an algorithm for that problem with imprecise data we use the concept of minimizing the maximum regret. We present complexity results and some dominance properties. [ABSTRACT FROM AUTHOR]

In this work we study min max robust scheduling problems assuming that the processing times can take any value in the budgeted uncertainty set introduced by Bertsimas and Sim (2003, 2004). We consider problems on a single machine that minimize the (weighted and unweighted) sum of completion times and problems that minimize the makespan on parallel and unrelated machines. We provide approximation algorithms: constant factor, average non-constant factor, (fully or not) polynomial time approximation schemes. In addition, we prove that the robust version of minimizing the weighted completion time on a single machine is NP -hard in the strong sense. [ABSTRACT FROM AUTHOR]

Abstract We give an algorithm that for an input planar graph G of n vertices and an integer k , in min { O (n log 3 n) , O (n k 2) } time either constructs a branch-decomposition of G of width at most (2 + δ) k , where δ > 0 is a constant, or a (k + 1) × k + 1 2 cylinder minor of G implying bw (G) > k , where bw (G) is the branchwidth of G. This is the first O ̃ (n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min { O (n 1 + ϵ) , O (n k 2) } (where ϵ > 0 is a constant) time constant-factor approximations. For a planar graph G and k = bw (G) , a branch-decomposition of width at most (2 + δ) k and a g × g 2 cylinder/grid minor with g = k β , where β > 2 is a constant, can be computed by our algorithm in min { O (n log 3 n log k) , O (n k 2 log k) } time. [ABSTRACT FROM AUTHOR]

Abstract The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set S of leaf labels and a set R of resolved triplets over S and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a 1 ∕ 4 -approximation in polynomial time. Next, we generalize Wu's exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted k -ary phylogenetic tree for any specified k ≥ 2 subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial-time approximation scheme (PTAS) for complete instances of MTC (meaning that for every S ′ ⊆ S with | S ′ | = 3 , R contains at least one rooted triplet involving the leaf labels in S ′), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered. [ABSTRACT FROM AUTHOR]

Abstract To face the explosion of the Internet traffic, a new generation of optical networks is being developed; the Elastic Optical Networks (EONs). EONs use the optical spectrum efficiently and flexibly, but that gives rise to more difficulty in the resource allocation problems. In this article, we study the problem of Spectrum Assignment (SA) in Elastic Optical Tree-Networks. Given a set of traffic requests with their routing paths (unique in the case of trees) and their spectrum demand, a spectrum assignment consists in allocating to each request an interval of consecutive slots (spectrum units) such that a slot on a given link can be used by at most one request. The objective of the SA problem is to find an assignment minimizing the total number of spectrum slots to be used. We prove that SA is NP-hard in undirected stars of 3 links and in directed stars of 4 links, and show that it can be approximated within a factor of 4 in general stars. Afterwards, we use the equivalence of SA with a graph coloring problem (interval coloring) to find constant-factor approximation algorithms for SA on binary trees with special demand profiles. [ABSTRACT FROM AUTHOR]

Abstract We first prove a new separating hyperplane theorem characterizing when a pair of compact convex subsets K , K ′ of the Euclidean space intersect, and when they are disjoint. The theorem, referred as distance duality , is distinct from classical separation theorems. Next, utilizing the theorem we develop a substantially generalized and stronger version of the Triangle Algorithm , originally designed for the convex hull membership problem. If δ ∗ = d (K , K ′) , the Euclidean distance between the sets, ρ ∗ the maximum of their diameters, and ε a prescribed tolerance, the Triangle Algorithm approximates δ ∗ , or induces a separating hyperplane, or approximates optimal supporting hyperplanes. Specifically, it computes (p , p ′) ∈ K × K ′ satisfying any of the following conditions desired: (1) d (p , p ′) ≤ ε d (p , v) , v ∈ K , or d (p , p ′) ≤ ε d (p ′ , v ′) , v ′ ∈ K ′ (when δ ∗ = 0); (2) the orthogonal bisector of p p ′ separates K from K ′ ; (3) d (p , p ′) − δ ∗ ≤ ε d (p , p ′) (when δ ∗ > 0); (4) the supporting hyperplanes orthogonal to p p ′ satisfy δ ∗ − d (H , H ′) ≤ ε d (p , p ′). The corresponding number of iterations to solve these are, O (1 ∕ ε 2) , O (ρ ∗ 2 ∕ δ ∗ 2) , and O (ρ ∗ 2 ∕ δ ∗ 2 ε) for the last two, all independent of K , K ′. The complexity in each iteration of the first two tasks is computing for a given pair of iterates (p , p ′) ∈ K × K ′ a pivot , i.e. v ∈ K with d (p , v) ≥ d (p ′ , v) , or v ′ ∈ K ′ with d (p ′ , v ′) ≥ d (p , v ′). For the last two the complexity of each iteration is either computing a pivot, or supporting hyperplanes (H , H ′) orthogonal to p p ′. In the worst-case the complexity of each iteration is solving a linear program over K or K ′. Special cases include when K and K ′ are convex hulls of finite sets, or polytopes described as the intersection of halfspaces. The corresponding problems include, linear and quadratic programming, SVM and more. In separate work we describe computational comparison between Triangle Algorithm, Frank–Wolfe, Gilbert's Algorithm, SMO, and more. Future work includes extensions to unbounded convex sets, non-Euclidean norms, also combinatorial and NP-complete problems. [ABSTRACT FROM AUTHOR]

Abstract We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using " t -spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t -spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time. [ABSTRACT FROM AUTHOR]

Abstract A set D ⊆ V is called a dominating set of G = (V , E) if | N G [ v ] ∩ D | ≥ 1 for all v ∈ V. The Minimum Domination problem is to find a dominating set of minimum cardinality of the input graph. In this paper, we study the Minimum Domination problem for star-convex bipartite graphs, circular-convex bipartite graphs and triad-convex bipartite graphs. It is known that the Minimum Domination Problem for a graph with n vertices can be approximated with an approximation ratio of ln n + 1. However, we show that for any ϵ > 0 , the Minimum Domination problem does not admit a (1 − ϵ) ln n -approximation algorithm even for star-convex bipartite graphs with n vertices unless NP ⊆ DTIME (n O (log log n) ). On the positive side, we propose polynomial time algorithms for computing a minimum dominating set of circular-convex bipartite graphs and triad-convex bipartite graphs, by making polynomial time Turing reductions from the Minimum Domination problem for these graph classes to the Minimum Domination problem for convex bipartite graphs. [ABSTRACT FROM AUTHOR]

Abstract We study a less-than-truckload (LTL) transportation network and investigate the potential benefits of implementing an integrated solution approach for shipment routing throughout this network. In LTL transportation, shipments are first delivered to local hubs to be consolidated, then transferred to another hub, and finally sent to their destinations. This routing planning process involves three routing decisions: (i) from origins to hubs,(ii) between hubs, and (iii) from hubs to destinations. These decisions are usually handled in a sequential manner due to the complexity of these individual problems, which may result in suboptimal solutions. In this study, we develop an integrated framework for solving all of these decision problems simultaneously. We propose an optimization-driven approach that can efficiently handle large instances with thousands of loads and provides solutions with significant cost savings over the sequential approach. [ABSTRACT FROM AUTHOR]

Abstract The rank aggregation problem has received significant recent attention within the computer science community. Its applications today range far beyond the original aim of building metasearch engines to problems in machine learning, recommendation systems and more. Several algorithms have been proposed for these problems, and in many cases approximation guarantees have been proven for them. However, it is also known that some Markov chain based algorithms (MC1, MC2, MC3, MC4) perform extremely well in practice, yet had no known performance guarantees. We prove supra-constant lower bounds on approximation guarantees for all of them. Nevertheless, we show that in particular ways, MC4 can be seen as a generalization of Copeland score. [ABSTRACT FROM AUTHOR]

Abstract A bounded-degree-1 set S in an undirected graph G = (V , E) is a vertex subset such that the maximum degree of G [ S ] is at most one. Given a graph G , the Maximum Bounded-Degree-1Set (Max 1-bds) problem is to find a bounded-degree-1 set S of maximum size in G.A notion related to bounded-degree sets is that of an s - plex used to define the cohesiveness of subgraphs in social networks. An s -plex S in a graph G = (V , E) is a vertex subset such that for each v ∈ S , deg G [ S ] (v) ≥ | S | − s. One can easily show that a graph G has a2-plex of size k iff the complement graph of G has a bounded-degree-1 set of size k. Both the Maximum 2-Plex problem and the Maximum Bounded-Degree-1 Set problem are NP-hard. We give a simple branch-and-reduce algorithm running in polynomial space and applying branching strategies with at most three branches for Max 1-bds. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time O ∗ (1. 461 3 n) which is faster than previous exact algorithms. Moreover, we show that the Max 1-bds problem cannot be approximated to a ratio greater than n ϵ − 1 in polynomial time for all ϵ > 0 unless P = NP. Some moderately exponential time approximation algorithms are given for Max 1-bds and its dual problem. [ABSTRACT FROM AUTHOR]

Abstract Let U be a set of colored objects, where the color of an object is an integer between 1 and n. Let P = { C 1 , ... , C n } be the partition of U into color classes, i.e., the set C i consists of all objects in U colored i. We study two families of problems on color classes, namely, rainbow problems and covering problems where the covering objects have a certain property. The goal in a rainbow problem is to select an optimal rainbow, subject to the conditions of the problem, where a rainbow is a subset of U that contains at most one object from each color class. For example, in the problem known as rainbow minmax gap the color classes are pairs of points on the x -axis, and one needs to select exactly one point from each color class (i.e., a complete rainbow), such that the maximum distance between a pair of consecutive selected points is minimized. This problem was studied by Consuegra and Narasimhan, who left the question of its complexity unresolved. We prove that it is NP-hard. For our proof we obtain the following auxiliary result. A 3-SAT formula is an LSAT formula if each clause (viewed as a set of literals) intersects at most one other clause, and, moreover, if two clauses intersect, then they have exactly one literal in common. We prove that the problem of deciding whether an LSAT formula is satisfiable or not is NP-complete. Using the LSAT result, we also prove that rainbow piercing and rainbow covering are NP-complete. In the covering problems that we consider, U is a set of points and only conflict-free objects are allowed, where an object is conflict free if it covers at most one point from each color class. The goal is to find a minimum-cardinality set of conflict-free objects that cover at least (or exactly) one point from each color class. We prove that problems in this family are NP-hard (or NP-complete) and present several constant-factor approximation algorithms. [ABSTRACT FROM AUTHOR]

Abstract We introduce the problem of Flexible Allocation on Related Machines with Assignment Restrictions (FARM). In this problem the input consists of a set of machines and a set of jobs. Each machine has a finite capacity, and each job has a resource requirement interval, a profit per allocated unit of resource, and a set of machines that can potentially supply the requirement. A feasible solution is an allocation of machine resources to jobs such that: (i) a machine resource can be allocated to a job only if it is a potential supplier of this job, (ii) the amount of machine resources allocated by a machine is bounded by its capacity, and (iii) the amount of resources that are allocated to a job is either in its requirement interval or zero. Notice that a job can be serviced by multiple machines. The goal is to find a feasible allocation that maximizes the overall profit. We focus on r - FARM in which the required resource of a job is at most an r -fraction of (or r times) the capacity of each potential machine, for some r ≥ 0. FARM is motivated by resource allocation problems arising in cellular networks and in cloud computing. Specifically, FARM models the problem of assigning clients to base stations in 4G cellular networks. We present a 2-approximation algorithm for 1- FARM and a 1 1 − r -approximation algorithm for r - FARM , for any r ∈ (0 , 1). Both are based on the local ratio technique and on maximum flow computations. We observe that an LP-rounding 2-approximation algorithm for the Generalized Assignment Problem also applies to 1- FARM. Finally, we give an Ω (r log r) lower bound on the approximation ratio for r - FARM (assuming P ≠ NP). [ABSTRACT FROM AUTHOR]

Abstract In this note, we study a dynamic vertex coloring for a graph G. In particular, one starts with a certain set of vertices black, and all other vertices white. Then, at each time step, a black vertex with exactly one white neighbor forces its white neighbor to become black. The initial set of black vertices is called a zero forcing set if by iterating this process, all of the vertices in G become black. The zero forcing number of G is the minimum cardinality of a zero forcing set in G , and is denoted by Z (G). Davila and Kenter have conjectured in 2015 that Z (G) ≥ (g − 3) (δ − 2) + δ where g and δ denote the girth and the minimum degree of G , respectively. This conjecture has been proven for graphs with girth g ≤ 10. In this note, we present a proof for g ≥ 5 , δ ≥ 2 , thereby settling the conjecture. [ABSTRACT FROM AUTHOR]

Abstract We demonstrate here that submodular minimization (SM) problems subject to constraints containing up to two variables per inequality, SM2, are 2-approximable in polynomial time and a better approximation factor cannot be achieved in polynomial time unless NP = P. The 2-approximation holds when either the constraints have the round-up property (the rounding up of a feasible fractional solution is feasible) or, if the constraints do not have this property, for monotone submodular functions. The submodular minimization or supermodular maximization on constraints where the coefficients of the two variables in each constraint are of opposite signs (monotone constraints) is solvable in polynomial time. The 2-approximability and the polynomial time solvability for monotone constraints hold also for multi-sets that contain elements with integer multiplicity greater than 1, except that the running time is then pseudo-polynomial in that it depends on the range of the variables. This complexity cannot be improved unless NP = P. Our results indicate that SM2 problems are not much harder than the respective linear integer problems on two variables per constraint: For monotone constraints both problems are polynomial time solvable, and for non-monotone NP-hard problems, both problems have 2-approximation algorithms. For SM2 problems the factor 2 approximation is provably best possible, whereas for the respective linear integer problems it has not been established that the factor 2 is best possible, but this has been conjectured. On the other hand, for SM2 problems where the two variables constraints' coefficients form a totally unimodular constraint matrix, the linear integer optimization problem is solved in polynomial time, whereas the submodular optimization is proved here to be NP-hard. The submodular minimization NP-hard problems for which our general purpose 2-approximation algorithm applies include submodular-vertex cover, submodular-2SAT, submodular-min satisfiability, submodular-edge deletion for clique, submodular-node deletion for biclique and others. [ABSTRACT FROM AUTHOR]

We study an edge coloring problem in multigraphs, in which each node incurs a cost equal to the number of appearances of the most frequent color among those received by its incident edges. We seek an edge coloring with a given number w of colors, that minimizes the total cost incurred by the nodes of the multigraph. We consider a class of approximation algorithms for this problem, which are based on orienting the edges of the multigraph, then grouping appropriately the incoming and outgoing edges at each node so as to construct a bipartite multigraph of maximum degree w , and finally obtaining a proper edge coloring of this bipartite multigraph. As shown by Nomikos et al. (2001), simply choosing an arbitrary edge orientation in the first step yields a 2-approximation algorithm. We investigate whether this approximation ratio can be improved by a more careful choice of the edge orientation in the first step. We prove that, assuming a worst-case bipartite edge coloring, this is not possible in the asymptotic sense, as there exists a family of instances in which any orientation gives a solution with cost at least 2 − Θ ( 1 w ) times the optimal. On the positive side, we show how to produce an orientation which results in a solution with cost within a factor of 2 − 1 2 w of the optimal, thus yielding an approximation ratio strictly better than 2. This improvement is important in view of the fact that this graph-theoretic problem models, among others, wavelength assignment to communication requests in multifiber optical star networks. In this context, the parameter w corresponds to the number of available wavelengths per fiber, which is limited in practice due to technological constraints. [ABSTRACT FROM AUTHOR]

The Sorting by Prefix Reversals problem consists in sorting the elements of a given permutation π using a minimum number of prefix reversals, i.e. reversals that always involve the leftmost element of π . A natural extension of this problem is to consider strings, in which any letter may appear several times, rather than permutations. In strings, three different types of problems arise: grouping (given a string S , transform it so that all identical letters are consecutive), sorting (a constrained version of grouping, in which the target string must be lexicographically ordered) and rearranging (given two strings S and T , transform S into T ). In this paper, we study these three problems, under an algorithmic viewpoint, in the setting where two operations, rather than one, are allowed: namely, prefix and suffix reversals — where a suffix reversal must always involve the rightmost element of the string. We first compare the “prefix reversals only” case to our case, before presenting a series of algorithmic results on these three problems concerning polynomiality, constant ratio approximation algorithms, NP-hardness and fixed-parameterized tractability. These results depend on the size k of the alphabet on which the strings are built, with a particular focus on small-sized alphabet instances (i.e., k = O ( 1 ) ) and big-sized alphabet instances (i.e. n − k = O ( 1 ) , where n is the length of the input string(s)). [ABSTRACT FROM AUTHOR]

An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ , for Δ ≥ 3 , is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the literature. We devise an almost tight fractional local ratio algorithm with approximation ratio Δ , which proves to be effective also in practice. Furthermore, we show that a simple greedy algorithm applied to K 1 , k -free graphs yields an approximation ratio 2 k − 3 . We explore the behavior of this algorithm on subclasses of chair-free graphs and we show that it yields an approximation ratio k when restricted to ( K 1 , k , chair ) -free graphs. [ABSTRACT FROM AUTHOR]

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P of points and a set D of geometric objects in the plane, the goal is to compute a small-sized subset of P that hits all objects in D . Recently Agarwal and Pan (2014) presented a near-linear time algorithm for the case where D consists of disks in the plane. The algorithm uses sophisticated geometric tools and data structures with large resulting constants. In this paper, we design a hitting-set algorithm for this case without the use of these data-structures, and present experimental evidence that our new algorithm has near-linear running time in practice, and computes hitting sets within 1.3-factor of the optimal hitting set. We further present dnet , a public source-code module that incorporates this improvement, enabling fast and efficient computation of small-sized hitting sets in practice. [ABSTRACT FROM AUTHOR]

We investigate two NP -complete vertex partition problems on edge-weighted complete graphs with 3 k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2- paths ) such that the total weight of the paths is maximized. We present a cubic time approximation algorithm that computes a 2-path partition whose total weight is at least . 5833 of the weight of an optimal partition, improving upon the ( . 5265 − ϵ ) -approximation algorithm of Tanahashi and Chen (2010). Restricting the input to graphs with edge weights in { 0 , 1 } , we present a . 75 approximation algorithm improving upon the . 55 -approximation algorithm of Hassin and Schneider (2013). Combining this algorithm with a previously known approximation algorithm for the 3-Set Packing problem, we obtain a . 6 -approximation algorithm for the problem of partitioning a { 0 , 1 } -edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights is due to Chen and Tanahashi (2009) and achieves an approximation ratio of . 5257 . [ABSTRACT FROM AUTHOR]

We consider a problem of dispersing points on disjoint intervals on a line. Given n pairwise disjoint intervals sorted on a line, we want to find a point in each interval such that the minimum pairwise distance of these points is maximized. Based on a greedy strategy, we present a linear time algorithm for the problem. Further, we also solve in linear time the cycle version of the problem where the intervals are given on a cycle. [ABSTRACT FROM AUTHOR]

We study a combinatorial problem arising from the microarray synthesis. The objective of the Border Minimization Problem (BMP) is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the “border length” is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. An exponential time algorithm has been proposed for the problem but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and approximation algorithms. We show that BMP, P-BMP, and 1D-BMP are all NP-hard and 1D-BMP is polynomial time solvable. The interesting implications include (i) the BMP is NP-hard regardless of the dimension (1D or 2D) of the array; (ii) the array dimension differentiates the complexity of the P-BMP; and (iii) for 1D array, whether placement is given differentiates the complexity of the BMP. Another contribution of the paper is devising approximation algorithms, and in particular, we present a randomized approximation algorithm for BMP with approximation ratio O ( n 1 ∕ 4 log 2 n ) , where n is the total number of sequences. [ABSTRACT FROM AUTHOR]

Minimum spanning cactus and minimum spanning cactus extension problems are studied. Both problems are NP-Complete. We present an approximation algorithm for the minimum spanning cactus extension of a forest, a hardness of approximation result of the general minimum spanning cactus problem. For the minimum spanning cactus extension problem, Kabadi and Punnen presented polynomial time algorithms for extending quasi-stars, spanning trees (Kabadi and Punnen, 2013). We present improved analysis of their algorithms in both cases. We further show that their algorithm for the extension of spanning trees can be generalized to extend any connected spanning partial cactus. As a requirement of improved implementation, we have presented a new O ( n 3 ) algorithm to compute all minimum cost monotone paths with respect to a spanning tree. [ABSTRACT FROM AUTHOR]

In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0–1 knapsack in which all the item weights are equal to 1. Its deterministic version has an O ( n ) -time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided. [ABSTRACT FROM AUTHOR]

We address the problem of computing distances between permutations that take into account similarities between elements of the ground set dictated by a graph. The problem may be summarized as follows: Given two permutations and a positive cost function on transpositions that depends on the similarity of the elements involved, find a smallest cost sequence of transpositions that converts one permutation into another. Our focus is on costs that may be described via special metric-tree structures. The presented results include a linear-time algorithm for finding a minimum cost decomposition for simple cycles and a linear-time 4 ∕ 3 -approximation algorithm for permutations that contain multiple cycles. The proposed methods rely on investigating a newly introduced balancing property of cycles embedded in trees, cycle-merging methods, and shortest path optimization techniques. [ABSTRACT FROM AUTHOR]

Using the characteristic property of chordal graphs that they are the intersection graphs of subtrees of a tree, Erich Prisner showed that every chordal graph admits an eccentricity 2 -approximating spanning tree. That is, every chordal graph G has a spanning tree T such that e c c T ( v ) − e c c G ( v ) ≤ 2 for every vertex v , where e c c G ( v ) ( e c c T ( v ) ) is the eccentricity of a vertex v in G (in T , respectively). Using only metric properties of graphs, we extend that result to a much larger family of graphs containing among others chordal graphs, the underlying graphs of 7-systolic complexes and plane triangulations with inner vertices of degree at least 7. Furthermore, based on our approach, we propose two heuristics for constructing eccentricity k -approximating trees with small values of k for general unweighted graphs. We validate those heuristics on a set of real-world networks and demonstrate that all those networks have very good eccentricity approximating trees. [ABSTRACT FROM AUTHOR]

Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is NP -complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path-forests if the number of arms and components, respectively, are fixed. Finally, we describe a polynomial time approximation algorithm with approximation factor 3 for general graphs. [ABSTRACT FROM AUTHOR]

Sweep coverage provides solutions for the applications in wireless sensor networks, where periodic monitoring is sufficient instead of continuous monitoring. The objective of the sweep coverage problem is to minimize the number of sensors required in order to guarantee sweep coverage for a given set of points of interest on a plane. Instead of using only mobile sensors for sweep coverage, use of both static and mobile sensors can be more effective in terms of energy utilization. In this paper, we introduce two variations in sweep coverage problem, where energy consumption by the sensors is taken into consideration. First, an energy efficient sweep coverage problem is proposed, where the objective is to minimize energy consumption by a set of sensors (mobile and/or static) with guaranteed sweep coverage. We prove that the problem is NP-hard and cannot be approximated within a factor of 2. An 8-approximation algorithm is proposed to solve the problem. A 2-approximation algorithm is also proposed for a special case. Second, an energy restricted sweep coverage problem is proposed, where the objective is to find the minimum number of mobile sensors to guarantee sweep coverage subject to the condition that the energy consumption by a mobile sensor in a given time period is bounded. We propose a ( 5 + 2 α ) -approximation algorithm to solve this NP-hard problem. [ABSTRACT FROM AUTHOR]

In the classical interval scheduling type of problems, a set of n jobs, characterized by their start and end time, needs to be executed by a set of machines, under various constraints. In this paper we study a new variant in which the jobs need to be assigned to at most k identical machines, such that the minimum number of machines that are busy at the same time is maximized. This is relevant in the context of genome sequencing and haplotyping, specifically when a set of DNA reads aligned to a genome needs to be pruned so that no more than k reads overlap, while maintaining as much read coverage as possible across the entire genome. We show that the problem can be solved in time min O ( n 2 log k ∕ log n ) , O ( n k log k ) by using max-flows. We also give an O ( n log n ) -time approximation algorithm with approximation ratio ρ = k ⌊ k ∕ 2 ⌋ . [ABSTRACT FROM AUTHOR]

A total dominating set of an undirected graph G = ( V , E ) is a set S ⊆ V of vertices such that each vertex of G is adjacent to at least one vertex of S . A secure total dominating set of G is a set D ⊆ V of vertices such that D is a total dominating set of G and each vertex v ∈ V ∖ D is adjacent to at least one vertex u ∈ D with the property that the set ( D ∖ { u } ) ∪ { v } is a total dominating set of G . The secure total domination number γ s t ( G ) of G is the minimum cardinality of a secure total dominating set of G . We establish bounds on the secure total domination number. In particular, we show that every graph G with no isolated vertices satisfies γ s t ( G ) ≤ 2 α ( G ) , where α ( G ) is the independence number of G . Further, we study the problem of finding the secure total domination number. We show that the decision version of the problem is N P -complete for chordal bipartite graphs, planar bipartite graphs with arbitrary large girth and maximum degree 3, split graphs and graphs of separability at most 2. Finally, we show that the optimisation version of the problem can be approximated in polynomial time within a factor of c ln | V | for some constant c > 1 and cannot be approximated in polynomial time within a factor of c ′ ln | V | for some constant c ′ < 1 , unless P = N P . [ABSTRACT FROM AUTHOR]

Let G be a graph and u , v be any two distinct vertices of G . A vertex w of G resolves u and v if the distance between u and w does not equal the distance between v and w . A set W of vertices of G is a resolving set for G if every pair of vertices of G is resolved by some vertex of W . The minimum cardinality of a resolving set for G is the metric dimension , denoted by dim ( G ) . If G is a connected graph, then a vertex w strongly resolves two vertices u and v if there is a shortest u – w path containing v or a shortest v – w path containing u . A set S of vertices is a strong resolving set for G if every pair of vertices is strongly resolved by some vertex of S and the minimum cardinality of a strong resolving set is called the strong dimension of G and is denoted by sdim ( G ) . Both the problem of finding the metric dimension and the problem of finding the strong dimension of a graph are known to be NP-hard. It is known that the strong dimension can be polynomially transformed to the vertex covering problem for which good approximation algorithms are known. The metric dimension is a lower bound for the strong dimension. In this paper we compare the metric and strong dimensions of graphs. We describe all trees for which these invariants are the same and determine the class of trees for which the difference between these invariants is a maximum. We observe that there is no linear upper bound for the strong dimension of trees in terms of the metric dimension. For cographs we show that sdim ( G ) ≤ 3 dim ( G ) and that this bound is asymptotically sharp. It is known that the problem of finding the metric dimension of split graphs is NP-hard. We show that the strong dimension of connected split graphs can be found in polynomial time. [ABSTRACT FROM AUTHOR]

In 2004 Newman [43] suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans–Williamson algorithm to approximate the Max Cut problem (Goemans and Williamson, 1995). Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman (2004) [43] shows that her relaxation seems better suited for designing polynomial-time approximation algorithms for the (LOP) than the widely-studied standard polyhedral linear relaxations. In this paper we strengthen the relaxation proposed by Newman (2004) [43] and conduct a polyhedral study of the corresponding polytope. Furthermore we relate the relaxation to other linear and semidefinite relaxations for the (LOP) and for the Traveling Salesman Problem and elaborate on its connection to the Max Cut problem. [ABSTRACT FROM AUTHOR]

We consider the variant of the Two-Dimensional Bin Packing Problem in which items have to be obtained by a series of guillotine cuts and cannot be rotated. We present a heuristic algorithm based on partial enumeration, and computationally evaluate its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases. [ABSTRACT FROM AUTHOR]

We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm. [ABSTRACT FROM AUTHOR]

A set D ⊆ V of a graph G = ( V , E ) is called an open neighborhood locating–dominating set (OLD-set) if (i) N G ( v ) ∩ D ≠ 0̸ for all v ∈ V , and (ii) N G ( u ) ∩ D ≠ N G ( v ) ∩ D for every pair of distinct vertices u , v ∈ V . Given a graph G = ( V , E ) , the Min OLD-set problem is to find an OLD-set of minimum cardinality. Given a graph G = ( V , E ) and a positive integer k , the Decide OLD-set problem is to decide whether G has an OLD-set of cardinality at most k . The Decide OLD-set problem is known to NP-complete for general graphs. In this paper we extend the NP-completeness result of the Decide OLD-set problem by showing that it remains NP-complete for bipartite graphs, planar graphs, split graphs and doubly chordal graphs. We prove that the Decide OLD-set problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for the Min OLD-set problem in trees. We also propose a ( 2 + 3 ln Δ ) -approximation algorithm for the Min OLD-set problem and show that the Min OLD-set problem cannot be approximated within 1 2 ( 1 − ϵ ) ln | V | for any ϵ > 0 unless NP ⊆ DTIME ( | V | O ( log log | V | ) ) . Finally, we prove that the Min OLD-set problem is APX-complete for bipartite graphs of maximum degree 3. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the makespan of a schedule on m parallel machines of n jobs, where each job requires exactly one of s additional unit resources. This problem collapses to P ∥ C max if every job requires a different resource. It is therefore NP-hard even if we fix the number of machines to 2 and strongly NP-hard in general. Although very basic, its approximability is not known, and more general cases, such as scheduling with conflicts , are often not approximable. We give a ( 2 − 2 m + 1 ) -approximation algorithm for this problem, and show that when the deviation in jobs processing times is bounded by a ratio ρ , the same algorithm approximates the problem within a tight factor 1 + ρ ( m − 1 ) n . This problem appears in the design of download plans for Earth observation satellites, when scheduling the transfer of the acquired data to ground stations. Within this context, it may be required to process jobs by batches standing for the set of files related to a single observation. We show that there exists a ( 2 − 1 m ) -approximation algorithm respecting such batch sequences. Moreover, provided that the ratio ρ , between maximum and minimum processing times, is bounded by ⌊ s − 1 m − 1 ⌋ , we show that the proposed algorithm approximates the optimal schedule within a factor 1 + s − 1 n . [ABSTRACT FROM AUTHOR]

We consider generalizations of the connected facility location problem, where clients connect to open facilities via access trees that are shared by multiple clients. For each edge of these trees, a combination of several cable types can be chosen, according to the demand carried by the edge. The task is to choose open facilities, a Steiner tree among them as a core network, and access trees with appropriate cable types on their edges to connect clients to the open facilities in such a way that the sum of the facility opening costs and cable costs for the core and access networks is minimal. Problems of this type arise widely in the planning of access and distribution networks in telecommunications, logistics, or energy networks. In this paper, we introduce and analyze two fundamental versions of these problems. In the Buy-at-Bulk version of the problem, each access cable type has a fixed setup cost and a fixed capacity, whereas in the Deep-Discount problem version, each cable type has unlimited capacity but a traffic-dependent variable cost in addition to its fixed setup cost. We derive the first constant-factor approximation algorithms for these problems, using different algorithmic and analytical techniques. [ABSTRACT FROM AUTHOR]