Approximation hardness of dominating set problems in bounded degree graphs [PDF]
, 2008 We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. Using a similar result obtained by Trevisan for Minimum Set Cover we prove the first explicit approximation lower bounds for various
Chlebikova, Janka +4 more
core +1 more source
Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements [PDF]
, 2014 We consider degree bounded network design problems with element and vertex connectivity requirements. In the degree bounded Survivable Network Design (SNDP) problem, the input is an undirected graph G = (V, E) with weights w(e) on the edges and degree ...
Ali Vakilian +3 more
core +1 more source
Algorithms and error bounds for multivariate piecewise constant approximation [PDF]
, 2010 We review the surprisingly rich theory of approximation of functions of many vari- ables by piecewise constants. This covers for example the Sobolev-Poincar´e inequalities, parts of the theory of nonlinear approximation, Haar wavelets and tree ...
Oleg Davydov, Davydov, Oleg
core +1 more source
The Rate of Convergence for Linear Shape-Preserving Algorithms
Concrete Operators, 2015 We prove some results which give explicit methods for determining an upper bound for the rate of approximation by means of operators preserving a cone. Thenwe obtain some quantitative results on the rate of convergence for some sequences of linear shape ...
Boytsov Dmitry, Sidorov Sergei
doaj +1 more source
Complexity of approximating bounded variants of optimization problems [PDF]
, 2006 We study low degree graph problems such as Maximum Independent Set and Minimum Vertex Cover. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional ...
Chlebikova, Janka +3 more
core +1 more source
Lowest Degree k-Spanner: Approximation and Hardness [PDF]
, 2014 A k-spanner is a subgraph in which distances are approximately preserved, up to some given stretch factor k. We focus on the following problem: Given a graph and a value k, can we find a k-spanner that minimizes the maximum degree?
Chlamtác, Eden, Dinitz, Michael
core +1 more source
The degree of copositive approximation by polynomials [PDF]
Proceedings of the American Mathematical Society, 1983 Jackson type theorems are established for the approximation of a function f f that changes sign finitely many times in
openaire +1 more source
Asymptotics of the generalized Gegenbauer functions of fractional degree [PDF]
, 2020 The generalized Gegenbauer functions of fractional degree (GGF-Fs), denoted by rG (λ) ν (x) (right GGF-Fs) and lG (λ) ν (x) (left GGF-Fs) with x ∈ (−1, 1), λ > −1/2 and real ν ≥ 0, are special functions (usually non-polynomials), which are defined ...
Wang, Li-Lian, Liu, Wenjie
core +1 more source
Lower bounds for the degree of approximation [PDF]
Transactions of the American Mathematical Society, 1960 is the optimal degree of approximation of 2W. In this paper we shall give simple methods which permit to find the order of magnitude of Dn(W) for several important classes ?1: for some classes of analytic functions (?6); for the unit ball AP+a of the space CP+a of functions with continuous derivatives of order p, which satisfy a Lipschitz condition ...
openaire +1 more source
On the accuracy of the binomial approximation to the distance distribution of codes [PDF]
, 1995 The binomial distribution is a well-known approximation to the distance spectra of many classes of codes.
Krasikov, I, Litsyn, S
core +1 more source