Search

Abstract Let R be a finite set of terminals in a convex metric space (M , d). We give approximation algorithms for problems of finding a minimum size set S ⊆ M of additional points such that the unit-disc graph G [ R ∪ S ] of R ∪ S satisfies some connectivity properties. Let Δ be the maximum number of independent points in a unit ball. For the Steiner Tree with Minimum Number of Steiner Points problem we obtain approximation ratio 1 + ln ⁡ (Δ − 1) + ϵ , which in R 2 reduces to 1 + ln ⁡ 4 + ϵ < 2.3863 + ϵ ; this improves the ratios ⌊ (Δ + 1) / 2 ⌋ + 1 + ϵ of [19] and 2.5 + ϵ of [7] , respectively. For the Steiner Forest with Minimum Number of Steiner Points problem we give a simple Δ-approximation algorithm, improving the ratio 2 (Δ − 1) of [21]. We also simplify the Δ-approximation of [4] , when G [ R ∪ S ] should be 2-connected. Highlights • We consider connectivity problems on unit-disc graphs in a convex metric space. • Let Δ be the maximum number of independent points in a unit ball. • For Steiner Tree with Minimum Number of Steiner Points we improve the ratio (Δ + 1) / 2 to 1 + ln ⁡ (Δ − 1). • For Steiner Forest with Minimum Number of Steiner Points we improve the ratio 2 (Δ − 1) to Δ. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of trajectory planning of a mobile robot for pasture maintenance comprising mulching weeds, reseeding patches without vegetation and spreading cowpats. Based on the sensor-based acquired data (points of interest), the proposed approach is to first use an approximation algorithm for data clustering in the form of non-convex and convex hulls. These hulls are then delimited by stair-shaped limits with respect to the working width of the robot, and their centres of gravity calculated. To minimise the travelled distance between the centres of gravity of the defined areas, the Travelling Salesman Problem is addressed via an evolutionary algorithm. Finally, kinematic and dynamic properties of the robot are considered in order to generate the final trajectory. The capabilities of the proposed approaches are highlighted through the processing of several datasets. Graphical abstract (a)-Terestrial information about the field (b, c, d, e)-Sensor-based data about the field considering weed map, areas without vegetation and areas with cowpats (f)-Detail of the calculated path for the pasture robot based on convex hulls, centre of gravity, travelling salesman and evolutionary algorithm. Image 1 Highlights • Method development for selectively pasture maintenance with robotics. • Path planning for a mobile robot considering selectively pasture maintenance. • Data clustering based on approximation algorithm using non-convex and convex hulls. • Path optimization using evolutionary algorithm for Traveling Salesman Problem. • Trajectory calculation in respect of kinematic and dynamic properties of the robot. [ABSTRACT FROM AUTHOR]

If a closed subset of a Riemann surface is a set of uniform meromorphic approximation, then its boundary is shown to be a set of tangential meromorphic approximation. [ABSTRACT FROM AUTHOR]

We motivate and describe a new parameterized approximation paradigm which studies the interaction between approximation ratio and running time for any parametrization of a given optimization problem. As a key tool, we introduce the concept of an α - shrinking transformation , for α ≥ 1 . Applying such transformation to a parameterized problem instance decreases the parameter value, while preserving the approximation ratio of α (or α-fidelity ). Moving even beyond the approximation ratio, we call for a new type of approximative kernelization race . Our α -shrinking transformations can be used to obtain approximative kernels which are smaller than the best known for a given problem. The smaller “ α -fidelity” kernels allow us to obtain an exact solution for the reduced instance more efficiently, while obtaining an approximate solution for the original instance. We show that such fidelity preserving transformations exist for several fundamental problems, including Vertex Cover , d-Hitting Set , Connected Vertex Cover and Steiner Tree . [ABSTRACT FROM AUTHOR]

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0 . This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. [ABSTRACT FROM AUTHOR]

Abstract: Zero-order ultrasensitivity (ZOU) is a long known and interesting phenomenon in enzyme networks. Here, a substrate is reversibly modified by two antagonistic enzymes (a ‘push–pull' system) and the fraction in modified state undergoes a sharp switching from near-zero to near-unity at a critical value of the ratio of the enzyme concentrations, under saturation conditions. ZOU and its extensions have been studied for several decades now, ever since the seminal paper of Goldbeter and Koshland (1981); however, a complete probabilistic treatment, important for the study of fluctuations in finite populations, is still lacking. In this paper, we study ZOU using a modular approach, akin to the total quasi-steady state approximation (tQSSA). This approach leads to a set of Fokker–Planck (drift–diffusion) equations for the probability distributions of the intermediate enzyme-bound complexes, as well as the modified/unmodified fractions of substrate molecules. We obtain explicit expressions for various average fractions and their fluctuations in the linear noise approximation (LNA). The emergence of a ‘critical point’ for the switching transition is rigorously established. New analytical results are derived for the average and variance of the fractional substrate concentration in various chemical states in the near-critical regime. For the total fraction in the modified state, the variance is shown to be a maximum near the critical point and decays algebraically away from it, similar to a second-order phase transition. The new analytical results are compared with existing ones as well as detailed numerical simulations using a Gillespie algorithm. [Copyright &y& Elsevier]

Abstract: Consider -hulls, , from a dictionary of functions in space for . Their precise metric entropy orders are derived. Sparse linear approximation bounds are obtained to characterize the number of terms needed to achieve accurate approximation of the best function in a -hull that is closest to a target function. Furthermore, in the special case of , it is shown that a weak orthogonal greedy algorithm achieves the optimal approximation under an additional condition. [Copyright &y& Elsevier]

Abstract: Given a graph with a cost function and a vertex subset , an internal Steiner tree is a Steiner tree that contains all the vertices in , and such that each vertex in must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree whose total cost is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a -approximation algorithm for solving the problem on complete graphs, where is an approximation ratio for the Steiner tree problem. Currently, the best-known is . Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a -approximation algorithm for the problem. [Copyright &y& Elsevier]

Abstract: Given a graph of interactions, a module (also called a community or cluster) is a subset of nodes whose fitness is a function of the statistical significance of the pairwise interactions of nodes in the module. The topic of this paper is a model-based community finding approach, commonly referred to as modularity clustering, that was originally proposed by Newman (Leicht and Newman, 2008 [25]) and has subsequently been extremely popular in practice (e.g., see Agarwal and Kempe, 2008 [1], Guimer‘a et al., 2007 [20], Newman, 2006 [28], Newman and Girvan, 2004 [30], Ravasz et al., 2002 [32]). Various heuristic methods are currently employed for finding the optimal solution. However, as observed in Agarwal and Kempe (2008) [1], the exact computational complexity of this approach is still largely unknown. To this end, we initiate a systematic study of the computational complexity of modularity clustering. Due to the specific quadratic nature of the modularity function, it is necessary to study its value on sparse graphs and dense graphs separately. Our main results include a -inapproximability for dense graphs and a logarithmic approximation for sparse graphs. We make use of several combinatorial properties of modularity to get these results. These are the first non-trivial approximability results beyond the NP-hardness results in Brandes et al. (2007) [10]. [Copyright &y& Elsevier]

Abstract: In this paper modified variants of the sparse Fourier transform algorithms from Iwen (2010) [32] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, , in time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented. [Copyright &y& Elsevier]

Abstract: Node-Weighted Steiner Forest is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider the restriction to planar graphs where the problem remains NP-complete. Demaine et al. showed that the generic primal-dual algorithm of Goemans and Williamson is a 6-approximation on planar graphs. We present (1) two different analyses to prove an approximation factor of 3, (2) show that our analysis is best possible for the chosen proof strategy, and (3) generalize this result to feedback problems on planar graphs. We give a simple proof for the first result using contraction techniques and following a standard proof strategy for the generic primal-dual algorithm. Given this proof strategy our analysis is best possible which implies that proving a better upper bound for this algorithm, if possible, would require different proof methods. Then, we give a reduction on planar graphs of Feedback Vertex Set to Node-Weighted Steiner Tree, and Subset Feedback Vertex Set to Node-Weighted Steiner Forest. This generalizes our result to the feedback problems studied by Goemans and Williamson. For the opposite direction, we show how our constructions can be combined with the proof idea for the feedback problems to yield an alternative proof of the same approximation guarantee for Node-Weighted Steiner Forest. [Copyright &y& Elsevier]

Abstract: We present a new framework for the design of computationally-efficient and incentive-compatible mechanisms for combinatorial auctions. The mechanisms obtained via this framework are randomized, and obtain incentive compatibility in the universal sense (in contrast to the substantially weaker notion of incentive compatibility in expectation). We demonstrate the usefulness of our techniques by exhibiting two mechanisms for combinatorial auctions with general bidder preferences. The first mechanism obtains an optimal -approximation to the optimal social welfare for arbitrary bidder valuations. The second mechanism obtains an -approximation for a class of bidder valuations that contains the important class of submodular bidders. These approximation ratios greatly improve over the best (known) deterministic incentive-compatible mechanisms for these classes. [Copyright &y& Elsevier]

Abstract: We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems. [ABSTRACT FROM AUTHOR]

Abstract: We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone from Post''s lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions for the complexity class . This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP. [Copyright &y& Elsevier]

Abstract: We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C1P. [Copyright &y& Elsevier]

Abstract: When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be embedded in any truthful mechanism (e.g. VCG-like payment rules will not ensure truthfulness). We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where each bidder desires a specific known subset of items and only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann, O''Callaghan, and Shoham, who presented greedy heuristics. We show how to use If-Then-Else constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several canonical types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios. [Copyright &y& Elsevier]

Abstract: We study the problem of scheduling unit size jobs on n processors connected by a ring. We show a distributed algorithm for this problem with an approximation ratio of . [Copyright &y& Elsevier]

Abstract: Let S be a set of n points in the plane. We derive algorithms for approximating S by a step function of size k < n, i.e., by an x-monotone rectilinear polyline with k < n horizontal segments. We use the vertical distance to measure the quality of the approximation, i.e., the maximum distance from a point in S to the horizontal segment directly above or below it. We consider two types of problems: min-ε, where the goal is to minimize the error for a given number of horizontal segments k and min-#, where the goal is to minimize the number of segments for a given allowed error ε. After O (n) preprocessing time, we solve instances of the latter in O (min{k log n, n}) time per instance. We can then solve the former problem in O (min{n 2, nk log n}) time. Both algorithms require O (n) space. Our second contribution is an approximation algorithm for the min-ε problem that computes a solution within a factor of 3 of the optimal error for k segments, or with at most the same error as the k-optimal but using 2k −1 segments. Furthermore, experiments on real data show even better results than what is guaranteed by the theoretical bounds. Both approximations run in O (n log n) time and O (n) space. [Copyright &y& Elsevier]

Abstract: In TSP with neighborhoods (TSPN) we are given a collection of regions in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the neighborhoods are of approximately the same size. In this paper we present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat neighborhoods of arbitrary size. We also show that in the general case, where the neighborhoods can overlap and are not required to be convex or fat, TSPN is APX-hard and cannot be approximated within a factor of in polynomial time, unless . [Copyright &y& Elsevier]

We consider approximations of the form n1−o(1) for the Maximum Clique problem, where n is the number of vertices in the input graph and where the “o(1)” term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability results, have interesting consequences for exact computation. A simple sampling method underlies most of our results. [Copyright &y& Elsevier]

We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths (EDP) problem, we are given a network G with source–sink pairs (si,ti), 1&les;i&les;k, and the goal is to find a largest subset of source–sink pairs that can be simultaneously connected in an edge-disjoint manner. We show that in directed networks, for any &epsiv;>0, EDP is NP-hard to approximate within m1/2−&epsiv;. We also design simple approximation algorithms that achieve essentially matching approximation guarantees for some generalizations of EDP. Another related class of routing problems that we study concerns EDP with the additional constraint that the routing paths be of bounded length. We show that, for any &epsiv;>0, bounded length EDP is hard to approximate within m1/2−&epsiv; even in undirected networks, and give an O(√ of m)-approximation algorithm for it. For directed networks, we show that even the single source–sink pair case (i.e. find the maximum number of paths of bounded length between a given source–sink pair) is hard to approximate within m1/2−&epsiv;, for any &epsiv;>0. [Copyright &y& Elsevier]

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.''s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem. [Copyright &y& Elsevier]

Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case. [Copyright &y& Elsevier]

We obtain the following new coloring results:

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the minimum number of lines parallel to the x and y axes. We provide a 2-approximation algorithm, while the best known approximation ratio for this problem is O(logn). This algorithm is then extended to a 4-approximation algorithm for the rectilinear partitioning problem, which, given an mx × my array of nonnegative integers and positive integers v, h, asks to find a set of v vertical and h horizontal lines such that the maximum load of a subrectangle (i.e., the sum of the numbers in it) is minimized. The best known approximation ratio for this problem is 27. Our approximation ratio 4 is close to the best possible, as it is known to be NP-hard to approximate within any factor less than 2. The results are then extended to the d-dimensional space for d ≥ 2, where a d-approximation algorithm for the stabbing problem and a dd-approximation algorithm for the partitioning problem are developed. [Copyright &y& Elsevier]

The main result of this paper is a (2 + &epsiv;)-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n2) time 8-approximation algorithm for this problem and then extend it to an O(n3 + 6/&epsiv;n⌈+ 1⌉m) time (2 + &epsiv;)-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + &epsiv;)-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs. [Copyright &y& Elsevier]