# Questions tagged [approximation-algorithms]

An approximation algorithm is an algorithm that finds an approximate solution to a (typically NP-hard) problem. The quality of the algorithm is measured by how close to the actual optimum it performs. For example, it is a constant factor approximation algorithm if it always outputs a solution that is within a constant factor of the optimum. Hardness of approximation is one way to separate NP-hard problems.

136 questions
Filter by
Sorted by
Tagged with
665 views

885 views

### Approximating e with 2s and 3s

How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to e as possible? For example: ...
457 views

### Approximating derivatives between gridpoints

Suppose we have a grid (possibly irregular) of $N$ function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more). What would be a good way to ...
264 views

### Approximate homology of a large simplicial complex

I can use software to calculate the Betti numbers $\beta_0,\beta_1,\beta_2,\dots$ of a finite simplicial complex. This is prohibitive for large complexes, built on say > 100,000 nodes. Is there some ...
435 views

The (generalised) sign-rank of a (generalised) sign pattern $S\in \{+,-,0\}^{n\times m}$ is the minimum rank of all matrices with the same sign pattern, i.e. $$\min\left\{\operatorname{rank}(M)\ :\ M\... 2answers 327 views ### Approximating the action of the U(N) exponential map Let's say that I have a curve in \mathbb{C}^N given by the action of the unitary group:$$x(t) = e^{Ht}x_0,~ H \in \mathfrak{u}(N),~ ||x_0||=1$$Here, H is an NxN skew-Hermitian matrix (for very ... 0answers 394 views ### Any approximation algorithms for self-avoiding walks? I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ... 2answers 672 views ### Getting started: combinatorial optimization for computer scientists I have a background in computer science and I am starting to work on some problems those are basically combinatorial optimization problems. I have good knowleges of graphs, *-flow algorithms and so ... 2answers 605 views ### Runge-Kutta method with c<1 In trying to solve an ODE y'=f(y,t) with a function f that is discontinuous at a subset (codim=1) of \mathbb R^n, I am looking for a Runge-Kutta ODE method whose stages do not evaluate f(x,t) at ... 1answer 1k views ### Lovász \delta condition for LLL Algorithm http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the \delta parameter for LLL bases called Lovász condition? ... 1answer 1k views ### Hypergraph Chromatic Number vs Degree, Clique-Size For a hypergraph let \chi be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let \Delta be ... 1answer 1k views ### Searching for an inhomogeneous diophantine approximation algorithm Given two nonzero real numbers x and y such that y/x is irrational, a real number z to be approximated, and a tolerance \epsilon, what is an algorithm that will provide coprime integers a ... 3answers 2k views ### How to make an approximation of path with polynom P(x,y)=0? Hi. Imagine that a user draws on the canvas any path. I want to approximate this path with a path P(x,y)=0 where P(x,y) - is unknown polynom. May be somebody can suggest an appropriate algorithm? ... 1answer 260 views ### Row-based iterative algorithms for computing the kernel of a matrix Suppose A is an m \times n matrix in the form$$A=\begin{pmatrix} — a_1 —\\ — a_2 —\\ \vdots \\ — a_m — \end{pmatrix}$$where a_i \in R^n is the i-th row of A. I know that it is possible ... 1answer 212 views ### What is the LP gap of vertex cover in planar graphs? What is the LP gap of vertex cover in planar graphs? The LP I refer to is min \sum_{e \in E } c_e x_e \ \  subject to  \ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E   c_e \geq 0  are ... 0answers 110 views ### Approximating a max-cut's intersection with other cuts (This is a cross-post from the Theoretical Computer Science Stack Exchange.) For the purposes of this question, a cut in a graph G is the edge-set \delta (S)\subseteq E(G) between some vertex-set ... 0answers 257 views ### envelope function for a linear combination of gaussian distributions Given a distribution F defined as a linear combination of Gaussian distributions: F = \sum_{i=1}^n C_i*N(\mu_i,\sigma_i) with \sum_{i=1}^n C_i = 1 I want to find a Gaussian function Q = a*e^{\... 4answers 2k views ### When we use Bernstein polynomials in application When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", "Simple ... 2answers 932 views ### Set Cover:Greedy vs LP Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks 2answers 328 views ### Can you solve this problem using a finite number of queries? Let g:[0,1]\to[0,1] be a continuous monotonically-increasing function. You can access g using queries of two kinds: Given x\in[0,1], return g(x). Given y\in[0,1], return g^{-1}(y). Given ... 3answers 3k views ### Construct the best piece-wise linear continuous function fitting given curve How to construct the optimal piece-wise linear continuous function fitting given curve and given number of knots (optimal knots positions also must be determined by this method)? 1answer 398 views ### Fast Bourgain embedding (or similar embeddings)? Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to l_2) to automatic feature engineering for machine learning/data science ( http://www.... 1answer 108 views ### complexity of bounded knapsack with spoilage Consider the usual bounded knapsack problem, with the extra twist: you know that k of the chosen items will get spoiled after the sack is packed. And this happens adversarially, i.e. k most ... 2answers 530 views ### Estimate size of graph by taking random walks Let G be a connected, finite graph and let v_0 be a vertex of G. I'm interested in methods of estimating the number of vertices in G, based on local exploration only. What I have in mind is: ... 1answer 674 views ### Practical error-estimates for (adaptive) Newton-Cotes Quadrature I am looking for practical error estimates for Newton-Cotes Quadrature rules. Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ... 0answers 130 views ### Approximation of integral of gaussian function over a parallelepiped Remark: I posted this question in math stackexchange here and computer science stackexchange https://cs.stackexchange.com/ few weeks ago but obtain no answer. Given a multi-dimensional gaussian ... 0answers 177 views ### Disjoint paths in temporal graphs Given a graph G=(V,E) and a pair of source-destination nodes s and t. Time is divided in periods with the total number of periods denoted by T. Each edge e is either operational or broken at ... 2answers 3k views ### Sparse approximation of the inverse of a sparse matrix Is it possible to approximate an inverse of a sparse matrix with a sparse matrix? The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ... 2answers 468 views ### How to check numerical precision of my computation of Stieltjes-constants? In a thread in MSE I proposed an older routine of mine for the efficient computation of coefficients; I use a very similar routine for the quick&dirty computation of the Stieltjes-constants. ... 2answers 526 views ### Approximation of curves When constructing minimax (sup-norm) polynomial approximations of real-valued functions, well-known results say (roughly speaking) that optimal solutions are characterized by the fact that they have ... 3answers 1k views ### iteratively (approximately) solving a sum of exponentials I would iteratively have to solve the following equation at iteration n: C = \sum_{1 \leq i \leq n}{e^{\frac{x_i}{T}}x_i} for T. Each iteration i an unknown x_i will be observed and C is ... 1answer 196 views ### Using Fourier Transform to speed up calculation of forces following an inverse square law Suppose I have n electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ... 3answers 113 views ### Detecting slow growth in a finite number of queries The following question was asked at Can you solve this problem using a finite number of queries? : Let g:[0,1]\to[0,1] be a continuous monotonically-increasing function. You can access g using ... 3answers 446 views ### Approximation of half-integers modified Bessel function of the second kind I am trying to optimise the calculation of the probability distribution poisson-inverse-gaussian its calculation involves a half-integers modified Bessel function of the second kind. Here's a formula ... 1answer 230 views ### Approximating John's ellipsoid from uniform sampling of a centrally symmetric convex polyhedron A centrally symmetric convex polyhedron in \Bbb R^n shifted from the origin with possibly e^{\alpha n} number of vertices at some \alpha>0 has an unique ellipsoid of maximum volume called ... 1answer 180 views ### Is there a Fourier Analytic way to approximate volume? Suppose a convex compact room in 3-dimensions is given and source and microphones recorders are provided in the room that can locate echo timings there are works in literature which can give you the ... 1answer 217 views ### computational complexity: do we gain acceleration? There is a technique we developed for series acceleration using the Wilf-Zeilberger method. Here is a simple Maple code in this regard, you need to download this too. The idea is you start with a WZ-... 0answers 23 views ### Do higher-order splines with Lipschitz derivatives exist on finite sets? Fix k\in \mathbb{N}^+ and let E=(e_i,f_i)_{i=1}^I\subset \mathbb{R}^n\times \mathbb{R}^m be a non-empty finite set with e_i\neq e_j whenever i\neq j. If n=m=1 then it's easy to see that:$$ ...
Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...