Search

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 + ϵ)-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/ϵn⌈+ 1⌉m) time (2 + ϵ)-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 + ϵ)-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]

Kernel based methods provide a way to reconstruct potentially high-dimensional functions from meshfree samples, i.e., sampling points and corresponding target values. A crucial ingredient for this to be successful is the distribution of the sampling points. Since the computation of an optimal selection of sampling points may be an infeasible task, one promising option is to use greedy methods. Although these methods may be very effective, depending on the specific greedy criterion the chosen points might quickly lead to instabilities in the computation. To circumvent this problem, we introduce and investigate a new class of stabilized greedy kernel algorithms, which can be used to create a scale of new selection strategies. We analyze these algorithms, and in particular we prove convergence results and quantify in a precise way the distribution of the selected points. These results allow to prove, in the case of certain Sobolev kernels, that the algorithms have optimal stability and optimal convergence rates, including for functions outside the native space of the kernel. The results also apply to the case of the usual P -greedy algorithm, significantly improving state-of-the-art results available in the literature. Illustrative experiments are presented that support the theoretical findings and show improvements of the stabilized algorithms in terms of accuracy due to improved stability. [ABSTRACT FROM AUTHOR]

The Min Label s - t Cut problem is a fundamental problem in combinatorial optimization. This problem comes from many applications in real world, for example, information security and computer networks. We study two linear programs for Min Label s - t Cut , proving that both of them have large integrality gaps, namely, Ω (m) and Ω (m 1 / 3 − ϵ) for the respective linear programs, where m is the number of edges in the input graph of the problem and ϵ > 0 is any arbitrarily small constant. As Min Label s - t Cut is NP-hard and the linear programming technique is a main approach to design approximation algorithms, our results give negative answer to the hope that designs can be found for better approximation algorithms for Min Label s - t Cut that purely rely on linear programming. [ABSTRACT FROM AUTHOR]

Results on two different settings of asymptotic behavior of approximation characteristics of individual functions are presented. First, we discuss the following classical question for sparse approximation. Is it true that for any individual function from a given function class its sequence of errors of best sparse approximations with respect to a given dictionary decays faster than the corresponding supremum over the function class? Second, we discuss sparse approximation by greedy type algorithms. We show that for any individual function from a given class we can improve the upper bound on the rate of convergence of the error of approximation by a greedy algorithm if we use some information from the previous iterations of the algorithm. Bounds of this type fall in the category of a posteriori bounds. [ABSTRACT FROM AUTHOR]

This paper proposes to apply coarse-grained parallel genetic algorithm (CGPGA) to solve polygonal approximation problem. Chromosomes are used to represent digital curves and genes correspond to points of curves. This method divides the whole population into several subpopulations, each of which performs evolutionary process independently. After every migration interval number of generations, these subpopulations exchange their information with each other. Inspired by the designing theory of ensemble learning in machine learning, this paper further improves the basic CGPGA through adopting different but effective genetic algorithms, respectively, in different subpopulations. Both the diversity among different subpopulations and the accuracy in each individual subpopulation are ensured. Experimental results, based on four benchmark curves and four real image curves extracted from the lake maps, show that the basic CGPGA outperforms the used genetic algorithm, and further the improved CGPGA (ICGPGA) is more effective than the basic CGPGA, in terms of the quality of best solutions, the average solutions, and the variance of best solutions. Especially for those larger approximation problems, the ICGPGA is more remarkably superior to some representative genetic algorithms. [ABSTRACT FROM AUTHOR]

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles. For fixed positive integer d , and positive integer ω , a graph G = (V , E) is a (d -dimensional) LoS network with range parameter ω if it can be embedded in a finite cube of the d -dimensional integer grid so that each pair of vertices in V are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than ω. In this paper we investigate a dynamic programming (DP) approach which can be used to obtain efficient algorithmic solutions for various combinatorial problems in LoS networks. In particular DP solves the Maximum Independent Set (MIS) problem in LoS networks optimally, for any ω , on narrow LoS networks (i.e. networks which can be embedded in a k × k ... × k × n region, for some fixed k independent of n). In the unrestricted case it has been shown that the (decision version of the) problem is NP-hard when 2 < ω = O (n 1 − δ) , for fixed 0 < δ < 1. We describe how DP can be used as a building block in the design of good approximation algorithms in this case. In particular we present a semi-online polynomial-time approximation scheme for the MIS problem in narrow d -dimensional LoS networks, as well as a polynomial-time 2-approximation algorithm and a fast polynomial time approximation scheme for the MIS problem in arbitrary d -dimensional LoS networks. Finally we comment on how the approach can be adapted to prove similar results for a number of important optimization problems in LoS networks. [ABSTRACT FROM AUTHOR]