Search

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 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 We study several variations of line segment covering problem with axis-parallel unit squares in the plane. Given a set S of n line segments, the objective is to find the minimum number of axis-parallel unit squares that cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP -complete, and give constant-factor approximation algorithms for those problems. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a 16-approximation algorithm based on multilevel linear programming relaxation technique. More precisely, we reduce this problem to the problem of covering points in the plane by a given set of unit squares using linear programming relaxation technique. A linear programming-based 8-approximation algorithm for the later problem yields a 16-approximation result for the former problem. This technique may be of independent interest in solving some other problems. [ABSTRACT FROM AUTHOR]

Abstract The maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a (1 − ε) -approximation for two agents, and a (8 / 9 − ε) -approximation for three agents. Apart from the extension to matroids, the (8 / 9 − ε) -approximation for three agents improves on a (7 / 8 − ε) -approximation by Amanatidis et al. (ICALP 2015). Some special cases are also presented and some extensions of the model are discussed. [ABSTRACT FROM AUTHOR]

Abstract This paper considers a class of nonlinear filtering algorithms based on variational Bayesian (VB) theory to settle the unknown measurement noise problem in target tracking system. When the unknown measurement noise is conditionally independent of states, based on the variational idea, estimate of probability density function of state is converted into approximation two probability density functions for both unknown noise and nonlinear states. Then, an iterative algorithm is established to jointly estimate the state and the unknown measurement noise using variational Bayesian inference. Thus, the unknown measurement noise could be estimated as hidden state. The convergence result of the proposed nonlinear probability density function approximation algorithm is also given. The simulation results of typical examples show that the proposed VB based methods have superior performance to these classic algorithms in target tracking problems. [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]

In this paper, we consider a variation of the classic dominating set problem - The Two Disjoint Connected Dominating Sets (DCDS) problem, which finds applications in many real domains including wireless sensor networks. In the DCDS problem, we are given a graph G = ( V , E ) and required to find a new edge set E ′ with minimum cardinality such that the resulting new graph after the adding of E ′ has a pair of disjoint connected dominating sets. This problem is very hard in general graphs, and we show that it is NP -hard even restricted to trees. We also present a polynomial time approximation algorithm for the DCDS problem for arbitrary trees with performance ratio 3 2 asymptotically. [ABSTRACT FROM AUTHOR]

We present the spatial discretization of the nonlinear convective flux in the incompressible Navier–Stokes equations using local boundary-value problems. The finite-volume discretization of the incompressible Navier–Stokes equations over staggered grids requires the approximation of the cell-face velocity components. In the proposed method, the cell-face velocity components are computed from local boundary-value problems, with the pressure gradient and the gradient of the transverse flux as source terms. The approximation is expressed as the sum of the homogeneous part, corresponding to the convection–diffusion operator, and the inhomogeneous part, corresponding to the source terms. The homogeneous part of the approximation is shown to be a weighted average of the central and the upwind approximation and thus, is first-order convergent over coarse grids and second-order over finer grids. We show that the inhomogeneous part of the approximation effectively removes the numerical diffusion introduced by the homogeneous part. The inclusion of the source terms in the local boundary-value problem results in a more accurate approximation that shows uniform second-order convergence and does not introduce any spurious oscillations. [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]

In the Canadian traveler problem, we are given an edge weighted graph with two specified vertices s and t and a probability distribution over the edges that tells which edges are present. The goal is to minimize the expected length of a walk from s to t . However, we only get to know whether an edge is active the moment we visit one of its incident vertices. Under the assumption that the edges are active independently, we show NP-hardness on series-parallel graphs and give results on the adaptivity gap. We further show that this problem is NP-hard on disjoint-path graphs and cactus graphs when the distribution is given by a list of scenarios. We also consider a special case called the multi-target graph search problem. In this problem, we are given a probability distribution over subsets of vertices. The distribution specifies which set of vertices has targets. The goal is to minimize the expected length of the walk until finding a target. For the independent decision model, we show that the problem is NP-hard on trees and give a ( 3.59 + ϵ ) -approximation for trees and a ( 14.4 + ϵ ) -approximation for general metrics. For the scenario model, we show NP-hardness on star graphs. [ABSTRACT FROM AUTHOR]

We provide a construction of an implementable method based on path-independent adaptive step-size control for global approximation of jump-diffusion SDEs. The sampling points are chosen in nonadaptive way with respect to trajectories of the driving Poisson and Wiener processes. However, they are adapted to the diffusion and jump coefficients of the underlying stochastic differential equation and to the values of intensity function of the driving Poisson process. The method is asymptotically optimal in the class of methods that use (possibly) non-equidistant discretization of the interval [ 0 , T ] and is more efficient than any method based on the uniform mesh. [ABSTRACT FROM AUTHOR]

We analyze the computational complexity of the problem of optimally managing a storage device connected to a source of renewable energy, the power grid, and a household (or some other form of energy demand) in the presence of uncertainty. We provide a mathematical formulation for the problem as a Markov decision process following other models appearing in the literature, and study the complexity of determining a policy to achieve the maximum profit that can be attained over a finite time horizon, or simply the value of such profit. We show that if the problem is deterministic, i.e. there is no uncertainty on prices, energy production, or demand, the problem can be solved in strongly polynomial time. This is also the case in the stochastic setting if energy can be sold and bought for the same price on the spot market. If the sale and buying price are allowed to be different, the stochastic version of the problem is #P-hard, even if we are only interested in determining whether there exists a policy that achieves positive profit. Furthermore, no constant-factor approximation algorithm is possible in general unless P = NP. However, we provide a Fully Polynomial-Time Approximation Scheme (FPTAS) for the variant of the problem in which energy can only be bought from the grid, which is #P-hard. [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]

In this work, we calculate a tight relaxed triangle inequality ratio for some of the most well-known indexes used in finding dissimilarities between two finite sets known as the Sørensen–Dice and Tversky indexes. This relaxed triangle inequality ratio affects efficiency and approximation ratios of recent algorithms for many combinatorial problems such as traveling salesman and nearest neighbor search. Because of that, there are many works providing ratios for several other indexes. In this work, we focus on the Tversky index, which is a generalization of many dissimilarity indexes commonly used in practice. We provide the tight ratio of the Tversky index in this paper. Because the Sørensen–Dice index is a special case of the Tversky index, we know from the results that the tight ratio for the Sørensen–Dice index is equal to 1.5. [ABSTRACT FROM AUTHOR]

This paper presents a new family of methods for evaluating matrix polynomials more efficiently than the state-of-the-art Paterson–Stockmeyer method. Examples of the application of the methods to the Taylor polynomial approximation of matrix functions like the matrix exponential and matrix cosine are given. Their efficiency is compared with that of the best existing evaluation schemes for general polynomial and rational approximations, and also with a recent method based on mixed rational and polynomial approximants. For many years, the Paterson–Stockmeyer method has been considered the most efficient general method for the evaluation of matrix polynomials. In this paper we show that this statement is no longer true. Moreover, for many years rational approximations have been considered more efficient than polynomial approximations, although recently it has been shown that often this is not the case in the computation of the matrix exponential and matrix cosine. In this paper we show that in fact polynomial approximations provide a higher order of approximation than the state-of-the-art computational methods for rational approximations for the same cost in terms of matrix products. [ABSTRACT FROM AUTHOR]

We study the polynomial time approximation of the NP -hard max k - vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 2 3 and 34 47 ≈ 0 . 72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio ( 1 − 1 e ) ≈ 0 . 632 . Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for max k - vertex cover compete with linear programming ones? [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]

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]

A set of intervals is independent when the intervals are pairwise disjoint. In the interval selection problem we are given a set I of intervals and we want to find an independent subset of intervals of largest cardinality. Let α ( I ) denote the cardinality of an optimal solution. We discuss the estimation of α ( I ) in the streaming model, where we only have one-time, sequential access to the input intervals, the endpoints of the intervals lie in { 1 , … , n } , and the amount of the memory is constrained. For intervals of different sizes, we provide an algorithm in the data stream model that given ε ∈ ( 0 , 1 / 2 ) computes an estimate α ˆ of α ( I ) that, with probability at least 2/3, satisfies 1 2 ( 1 − ε ) α ( I ) ≤ α ˆ ≤ α ( I ) . For same-length intervals, we provide another algorithm in the data stream model that given ε ∈ ( 0 , 1 / 2 ) computes an estimate α ˆ of α ( I ) that, with probability at least 2/3, satisfies 2 3 ( 1 − ε ) α ( I ) ≤ α ˆ ≤ α ( I ) . The space used by our algorithms is bounded by a polynomial in ε − 1 and log ⁡ n . We also show that no better estimations can be achieved using o ( n ) bits of storage. We also develop new approximate solutions to the interval selection problem, where the intervals have real endpoints and we want to report a feasible solution, that use O ( α ( I ) ) space. Our algorithms for the interval selection problem match the optimal results by Emek, Halldórsson and Rosén [Space-Constrained Interval Selection, TALG 2016], but are much simpler. [ABSTRACT FROM AUTHOR]

Let P be an orthogonal polygon with n vertices. A sliding camera travels back and forth along an orthogonal line segment s ⊆ P corresponding to its trajectory . The camera sees a point p ∈ P if there is a point q ∈ s such that p q ‾ is a line segment normal to s that is completely contained in P . In the Minimum-Cardinality Sliding Cameras (MCSC) problem , the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i.e., every point in P can be seen by some sliding camera in S ), while in the Minimum-Length Sliding Cameras (MLSC) problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel. In this paper, we answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP -complete when P is allowed to have holes, and (iii) an O ( n 3 log ⁡ n ) -time 2-approximation algorithm for the MCSC problem on [NE]-star-shaped orthogonal polygons with n vertices (similarly, [NW]-, [SE]-, or [SW]-star-shaped orthogonal polygons). [ABSTRACT FROM AUTHOR]

In this paper, we introduce and investigate the Minimum Eccentricity Shortest Path (MESP) problem in unweighted graphs. It asks for a given graph to find a shortest path with minimum eccentricity. Let n and m denote the number of vertices and the number of edges of a given graph. We demonstrate that: • a minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line; • the MESP problem is NP-hard for planar bipartite graphs with maximum degree 3 and W[2]-hard for general graphs; • a shortest path of minimum eccentricity k can be computed in O ( n 2 k + 2 m ) time; • a 2-approximation, a 3-approximation, and an 8-approximation for the MESP problem can be computed in O ( n 3 ) time, in O ( n m ) time, and in O ( m ) time, respectively; • in a graph with a shortest path of eccentricity k , a k -dominating set can be found in n O ( k ) time. [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]

An edge-bicolored graph G = ( V , R ∪ B ) is called Red/Blue-split graph if there exists a partition I B and I R of V such that I B and I R are independent sets in ( V , B ) and ( V , R ) , respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and König–Egerváry graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP -hard and thus we look at them from algorithmic paradigms that are meant for coping with NP -hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17] . [ABSTRACT FROM AUTHOR]

Motivated by the bus escape routing problem in printed circuit boards, we study the following rectangle escape problem: given a set S of n axis-aligned rectangles inside an axis-aligned rectangular region R , extend each rectangle in S toward one of the four borders of R so that the maximum density over the region R is minimized. The density of each point p ∈ R is defined as the number of extended rectangles containing p . We show that the problem is hard to approximate to within a factor better than 3/2 in general. When the optimal density is sufficiently large, we provide a randomized algorithm that achieves an approximation factor of 1 + ε with high probability improving over the current best 4-approximation algorithm available for the problem. When the optimal density is one, we develop an exact algorithm that finds an optimal solution efficiently. We also provide approximation algorithms and inapproximability results for a restricted version of the problem where rectangles are allowed to escape toward only a subset of directions. [ABSTRACT FROM AUTHOR]

Let P be an orthogonal polygon with n vertices. A partition of P into rectangles is called conforming if it results from cutting P along a set of interior-disjoint line segments, each having both endpoints on the boundary of P . The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any orthogonal line segment inside P . In this paper, we consider the problem of finding a conforming partition of P with minimum stabbing number. We first give an O ( n log ⁡ n ) -time algorithm to solve the problem when P is a histogram. For an arbitrary orthogonal polygon (even with holes), we give an integer programming formulation of the problem and show that a simple rounding results in a 2-approximation algorithm for the problem. Finally, we show that the problem is NP -hard if P is allowed to have holes. [ABSTRACT FROM AUTHOR]

In this paper, a chaotic multiple instance learning tracker based on chaos theory for a robust and efficient online tracking is introduced. In this method, chaotic characteristics can be utilized for representing the target as well as the updating appearance model, which has not been used for the tracking task. The computational architecture of the method is organized as follows. (1) Chaotic representation: a chaotic model can capture the complex dynamics of the target region to train the weak classifiers. Our representation can balance the global and local features to handle fast motion, partial occlusion, and illumination changes. (2) Importance of instance: fractal dimension of the dynamic model can be adjusted as instance weight for efficient online learning. (3) Chaotic approximation: A robust chaotic approximation to update the appearance model is introduced, which is crucial to select the discriminative and robust features. Chaotic online learning quickly explores the feature space to update the appearance model of the target by means of a chaotic map. The experimental results reveal that the proposed method is more effective and robust than the state-of-the-art trackers on various challenging sequences. Indeed, the efficiency of the proposed method is attributed to its strong online updating of chaotic policy as well as desirable target representation of chaotic model. [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]

The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in ( 0 , 1 ] and the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important in practice and finds numerous applications in scheduling, routing and resource allocation problems. Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy rounding and has led to the development of several algorithmic techniques. In this survey we consider approximation and online algorithms for several classical generalizations of bin packing problem such as geometric bin packing, vector bin packing and various other related problems. There is also a vast literature on mathematical models and exact algorithms for bin packing. However, this survey does not address such exact algorithms. In two-dimensional geometric bin packing , we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. In d -dimensional vector bin packing , each item is a d -dimensional vector that needs to be packed into unit vector bins. This problem is of great significance in resource constrained scheduling and in recent virtual machine placement in cloud computing. We also consider several other generalizations of bin packing such as geometric knapsack, strip packing and other related problems such as vector scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting, and also mention results for several important special cases. We briefly mention related techniques used in the design and analysis of these algorithms. In the end we conclude with a list of open problems. [ABSTRACT FROM AUTHOR]

We consider how the orthology/paralogy information can be corrected in order to represent a gene tree, a problem that has recently gained interest in phylogenomics. Interestingly, the problem is related to the Minimum CoGraph Editing problem on the relation graph that represents orthology/paralogy information, where we want to minimize the number of edit operations on the given relation graph in order to obtain a cograph. In this paper we provide both theoretical and experimental results on the Minimum CoGraph Editing problem. On the theoretical side, we provide approximation algorithms for bounded degree relation graphs, for the general problem and for the problem restricted to deletion of edges. On the experimental side, we present a genetic algorithm for Minimum CoGraph Editing and we provide an experimental evaluation of the genetic algorithm on synthetic data. [ABSTRACT FROM AUTHOR]

We consider the k-Splittable Capacitated Network Design Problem (kSCND) in a graph G = ( V , E ) with edge weight w ( e ) ≥ 0 , e ∈ E . We are given a vertex t ∈ V designated as a sink, a cable capacity λ > 0 , and a source set S ⊆ V with demand d ( v ) ≥ 0 , v ∈ S . For any edge e ∈ E , we are allowed to install an integer number x ( e ) of copies of e . The kSCND asks to simultaneously send demand d ( v ) from each source v ∈ S along at most k paths to the sink t . A set of such paths can pass through an edge in G as long as the total demand along the paths does not exceed the capacity x ( e ) λ . The objective is to find a set P of paths of G that minimize the installing cost ∑ e ∈ E x ( e ) w ( e ) . In this paper, we propose a ( ( k + 1 ) / k + ρ ST ) -approximation algorithm to the kSCND, where ρ ST is any approximation ratio achievable for the Steiner tree problem . [ABSTRACT FROM AUTHOR]

We prove new results for approximating the Graphic TSP. Specifically, we provide a polynomial-time 9 7 -approximation algorithm for cubic bipartite graphs and a ( 9 7 + 1 21 ( k − 2 ) ) -approximation algorithm for k -regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs. [ABSTRACT FROM AUTHOR]

A standard way to approximate the distance between two vertices p and q in a graph is to compute a shortest path from p to q that goes through one of k sources, which are well-chosen vertices. Precomputing the distance between each of the k sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing k sources is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources. In this paper, we analyze the stretch factor F FPS of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that F FPS can be bounded in terms of the minimal value F ⁎ of the stretch factor obtained using an optimal placement of k sources as F FPS ⩽ 2 r e 2 F ⁎ + 2 r e 2 + 8 r e + 1 , where r e is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor r e is not an artefact of the analysis by providing a class of graphs for which F FPS ⩾ 1 2 r e F ⁎ . [ABSTRACT FROM AUTHOR]

Suppose n colored points with k colors in R d are given. The Smallest Color-Spanning Ball ( SCSB ) is the smallest ball containing at least one point of each color. As the computation of the SCSB in L p metric ( p ≥ 1 ) is time-consuming, we focus on approximately computing the SCSB in near-linear time. Initially, we propose a 3-approximation algorithm running in O ( n log ⁡ n ) time. This algorithm is then utilized to present a ( 1 + ε ) -approximation algorithm with the running time of O ( ( 1 ε ) d n log ⁡ n ) . We improve the running time to O ( ( 1 ε ) d n ) using randomized techniques. Afterward, spanning colors with two balls is studied. For a special case where d = 1 , there is an algorithm with O ( n 2 ) time. We demonstrate that for any ε > 0 under the assumption that SETH is true, no approximation algorithm running in O ( n 2 − ε ) time exists for the problem even in one-dimensional space. Nevertheless, we consider the L ∞ metric where a ball is an axis-parallel hypercube and present a ( 1 + ε ) -approximation algorithm running in O ( ( 1 ε ) 2 d ( n 2 k ) log 2 ⁡ n ) time which is remarkable when k is large. This time can be reduced to O ( ( 1 ε ) n 2 k log ⁡ n ) when d = 1 . [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling a set of n jobs on a single machine with parallel batching and with rejection being allowed. Two bi-criteria problems are considered: (a) minimize the makespan subject to the constraint that the total rejection cost does not exceed a given threshold, and (b) minimize the total rejection cost subject to the constraint that the makespan does not exceed a given threshold. For the case of a batching machine with infinite capacity (i.e., the batch size allowed on the machine is larger than or equal to the number of jobs), we assume that the jobs have release dates. We present an O ( n 2 ) -time 2-approximation algorithm for problem (a) and, in addition, we present dynamic programming algorithms and fully polynomial-time approximation schemes for both problems (a) and (b). For the case of a batching machine with finite capacity (i.e., the batch size allowed on the machine is less than the number of jobs), we assume that the jobs have identical release dates. We propose approximation algorithms for (a) and present dynamic programming algorithms and fully polynomial-time approximation schemes for both problems (a) and (b). [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of computing the 2-vertex-connected components of directed graphs. We present a new algorithm for solving this problem in O ( n m ) time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in O ( n m 2 ) time. In this paper, we investigate the relationship between 2-vertex-connected components and dominator trees. We also consider three applications of our new algorithm, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest 2-vertex-connected spanning subgraph of 2-vertex-connected directed graph. [ABSTRACT FROM AUTHOR]

In this paper, a recurrent perturbation fuzzy neural network (RPFNN) is used to online approximate an unknown nonlinear term in the system dynamics. A sine–cosine perturbed membership function is used to handle rule uncertainties when it is hard to exactly determine the grade of the value of fuzzy sets. Unlike type-2 fuzzy sets use an extra type reduction operation to find the output, the proposed RPFNN does not require heavy computational loading. Meanwhile, this paper proposes an intelligent dynamic sliding-mode neural control (IDSNC) system which is composed of a neural controller and an exponential compensator. The neural controller is designed as the main controller via dynamic sliding-mode approach, and the exponential compensator is designed to obtain a faster reaching time and a good robustness. The parameter adaptation laws of the IDSNC system are derived based on the Lyapunov function, so that the system stability can be guaranteed. Finally, the IDSNC system is applied to an inverted pendulum problem and a chaotic synchronization problem. The simulation results demonstrate that the IDSNC system can achieve favorable control performance and is robust against parameter variations and external disturbances. [ABSTRACT FROM AUTHOR]

We give the first logarithmic approximation for minimizing average flow-time of jobs in the subset parallel machine setting (also called the restricted assignment setting) under a single knapsack constraint. In a knapsack constraint setting, each job has a profit, and the set of jobs which get scheduled must have a total profit of at least a quantity Π. Our result extends the work of Gupta et al. (2009) [8] who considered the special case where the profit of each job is unity. Our algorithm is based on rounding a natural LP relaxation for this problem. In fact, we show that one can use techniques based on iterative rounding. [ABSTRACT FROM AUTHOR]

Being the unbalanced version of the famous Min s – t Cut problem, the Min k -Size s – t Cut problem asks to find a k -size s – t cut with the minimum capacity, where a k -size s – t cut means an s – t cut with its s -side having size at most k . This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k -Size s – t Cut problem is NP-hard and can be approximated within O ( log ⁡ n ) , where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k -Size s – t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k + 1 k + 1 − k ⁎ , where k ⁎ is the size of the s -side of an optimal solution. [ABSTRACT FROM AUTHOR]

Locating source of diffusion in networks is crucial for controlling and preventing epidemic risks. It has been studied under various probabilistic models. In this paper, we study source location from a deterministic point of view by modeling it as the minimum cost doubly resolving set (DRS) problem, which is a strengthening of the well-known metric dimension problem. Let G be an undirected graph on n vertices, where each vertex has a nonnegative cost. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of vertices u , v in G , there exist x , y ∈ S such that the difference of distances (in terms of number of edges) between u and x , y is not equal to the difference of distances between v and x , y . The minimum cost DRS problem consists of finding a DRS in G with minimum total cost. We establish Θ ( ln ⁡ n ) approximability of the minimum DRS problem on general graphs for both weighted and unweighted versions. This provides the first explicit lower and upper bounds on approximation for the minimum (cost) DRS, which are nearly tight. Moreover, we design the first known strongly polynomial time exact algorithms for the minimum cost DRS problem on general wheels and trees with additional constant k ≥ 0 edges. [ABSTRACT FROM AUTHOR]

For two positive integers m , k and a connected graph G = ( V , E ) with a nonnegative vertex weight function w , the balanced m -connected k -partition problem, denoted as BC m P k , is to find a partition of V into k disjoint nonempty vertex subsets ( V 1 , V 2 , … , V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m -connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G , k ) , that is, β m ⁎ ( G , k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) } , where the maximum is taken over all m -connected k -partition of G . In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2 , a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k , where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2 k -connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v . In the case that every vertex has weight at most W / k , we prove a lower bound β 2 ⁎ ( G , k ) ≥ W / ( 2 k − 1 ) for 2 k -connected interval graph G . (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2 k -connected interval graphs. [ABSTRACT FROM AUTHOR]

We study the following problem, introduced by Chung et al. in 2006. We are given, online or offline, a set of coloured items of different sizes, and wish to pack them into bins of equal size so that we use few bins in total (at most α times optimal), and that the items of each colour span few bins (at most β times optimal). We call such allocations ( α , β ) -approximate. As usual in bin packing problems, we allow additive constants and consider ( α , β ) as the asymptotic performance ratios. We prove that for ε > 0 , if we desire small α , no scheme can beat ( 1 + ε , Ω ( 1 / ε ) ) -approximate allocations and similarly as we desire small β , no scheme can beat ( 1.69103 , 1 + ε ) -approximate allocations. We give offline schemes that come very close to achieving these lower bounds. For the online case, we prove that no scheme can even achieve ( O ( 1 ) , O ( 1 ) ) -approximate allocations. However, a small restriction on item sizes permits a simple online scheme that computes ( 2 + ε , 1.7 ) -approximate allocations. [ABSTRACT FROM AUTHOR]

We study the computational complexity of the puzzle Quell. The goal is to collect pearls by sliding a droplet of water over them in a map that is a two-dimensional grid. Each cell of the grid is either a free space (possibly with a pearl in it) or an obstacle. In each move, the droplet slides in one of the four directions to the maximal extent, through the free spaces of the map and collecting all pearls along the way, until it is stopped by an obstacle. We show that any-Moves-all-Pearls (deciding whether it is possible to collect all the pearls using any number of moves) can be solved in polynomial time. In contrast, both any-Moves-max-Pearls (finding the maximum number of pearls that can be collected using any number of moves) and min-Moves-all-Pearls (finding the minimum number of moves required to collect all the pearls) are APX-hard, although the corresponding decision problems are in FPT. We also present a simple 2-approximation for any-Moves-max-Pearls , and leave open the question whether min-Moves-all-Pearls admits a polynomial-time constant approximation. [ABSTRACT FROM AUTHOR]

Given an edge-weighted graph G = ( V , E ) and a subset R of V , a Steiner tree of G is a tree which spans all the vertices in R . A full Steiner tree is a Steiner tree which has all the vertices of R as its leaves. The full Steiner tree problem is to find a full Steiner tree of G with minimum weight. In this paper we consider the full Steiner tree problem when G is a unit disk graph. We present a 20-approximation algorithm for the full Steiner tree problem in G . As for λ -precise unit disk graphs we present a ( 10 + 1 λ ) -approximation algorithm, where λ is the length of the shortest edge in G . [ABSTRACT FROM AUTHOR]

We consider the problem of counting straight-edge triangulations of a given set P of n points in the plane. Until very recently it was not known whether the exact number of triangulations of P can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of P can be computed in O*(2n) time [9], which is less than the lower bound of O(2.43n)O(2.43n) on the number of triangulations of any point set [30]. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by ? the output of our algorithm and by cncn the exact number of triangulations of P, for some positive constant c, we prove that cn=?=cn.2o(n). This is the first algorithm that in sub-exponential time computes a (1+o(1))(1+o(1))-approximation of the base of the number of triangulations, more precisely, c=?1/n=(1+o(1))c. Our algorithm can be adapted to approximately count other crossing-free structures on P, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees. [ABSTRACT FROM AUTHOR]

We study a geometric version of the Red-Blue Set Cover problem originally proposed by Carr et al. (2000) [1]: given a red point set, a blue point set, and a set of objects, we want to choose a subset of objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first polynomial-time approximation scheme (PTAS) for this case. The technique we use simplifies and unifies previous PTASs for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares. [ABSTRACT FROM AUTHOR]

Different than the conventional queueing systems, in spatial queueing systems (SQS) the service rate for each customer-server pairs differs and the server that intervenes for a specific customer is not known a priori, depending on the availability of servers at the moment a request was made. These features make the SQS computationally expensive (almost intractable for large scale) but at the same time more suitable for real-life problems with high reliability expectations. Emergency response and on-demand transportation systems are two similar systems that can be modeled with the SQS. In this research, we aim to solve facility location problems as SQS with stochastic demand and service time. The stochasticity concerned here is temporal and spatial, that emerges from the uncertainty in the demand and service time. In order to tackle this problem Larson (1974)’s 2 n hypercube queueing model (HQM) is extended to 3 n HQM. In this model, there are two different possible service types for each server: (i) service for locations in the proximity of a server (area of responsibility) and (ii) service for other locations where the first responsible server is busy during this event. In addition, to decrease the dimension of the problem, which is intractable due to their size, a new 3 n aggregate hypercube queueing model (AHQM) is developed that treats group of servers (bins) in a similar manner by considering interactions among bins. An efficient graph partitioning algorithm is proposed to cluster servers in groups with an objective to minimize the interactions among groups. Both exact and approximate approaches are integrated inside two optimization methods (i.e. variable neighborhood search and simulated annealing) to find server locations that improve system performance. Computational experiments showed that both models are applicable to use inside optimization algorithms to find good server locations and to improve system performance measures of SQS. [ABSTRACT FROM AUTHOR]

Some hard-to solve combinatorial problems of finding several disjoint discrete structures in complete weighted graph are considered. Efficient algorithms with performance guarantees are constructed for the Euclidean m -Peripatetic Salesman Problem, m -Weighted Clique Problem and m -Layer Planar three-index Assignment Problem. [ABSTRACT FROM AUTHOR]