# 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.

**1**

**0**answers

### Computational complexity of rate $\frac{1}{2}$ codes

**3**

**0**answers

### Do higher-order splines with Lipschitz derivatives exist on finite sets?

**1**

**0**answers

### what is the computational complexity of Louvain algorithm?

**-5**

**1**answer

### Lottery in O(1) per participant

**2**

**1**answer

### Min-sum and min-max node-disjoint path problems

**6**

**3**answers

### Approximating derivatives between gridpoints

**0**

**0**answers

### Norm of vector components optimization of linear matrix combination

**5**

**1**answer

### Row-based iterative algorithms for computing the kernel of a matrix

**0**

**0**answers

### How to derive space bound for Morris(a) approximate counting algorithm

**1**

**0**answers

### Why does Y. Moshe Vardi use this specific matrix when estimating source-destination traffic intensities with EM algorithm?

**0**

**0**answers

### A variant of travel salesman problem with charging points

**0**

**0**answers

### A variant of Steiner tree problem

**2**

**0**answers

### How to solve a QCQP where constraints are balls?

**1**

**0**answers

### Minimum delay path in time-dependent graph

**0**

**2**answers

### Minimal bottleneck path in time-varying graph

**7**

**1**answer

### Norms of B-spline coefficients

**3**

**3**answers

### Detecting slow growth in a finite number of queries

**4**

**2**answers

### Can you solve this problem using a finite number of queries?

**4**

**0**answers

### Disjoint paths in temporal graphs

**1**

**1**answer

### Reference Request: Randomly Generated Contraction

**1**

**0**answers

### Meaning of L-reduction from Dominating set problem

**6**

**1**answer

### Approximate homology of a large simplicial complex

**2**

**1**answer

### Subdividing a sequence such that sum is somewhat equally distributed

**1**

**0**answers

### Algorithmic combinatorial discrete problem (randomized lazy update?)

**2**

**2**answers

### Transforming an optimization problem to maxmin formulation

**0**

**0**answers

### Maximize sum of supermodular functions over nested sets

**4**

**1**answer

### Fast Bourgain embedding (or similar embeddings)?

**1**

**0**answers

### Adaptive Simpsons Quadrature Algorithm for Double Integrals? [closed]

**0**

**3**answers

### Im looking for an algorithm that can solve or approximate the solution to a problem

**1**

**0**answers

### Hutchinson-type algorithm for efficient computation of trace of inverse of non symmetric matrix

**1**

**0**answers

### What's the name of functions that produces a non deterministic solution without losing the exact solution?

**5**

**1**answer

### What is the LP gap of vertex cover in planar graphs?

**3**

**3**answers

### Approximation of half-integers modified Bessel function of the second kind

**1**

**0**answers

### How to compress variables in a linear regression

**3**

**2**answers

### Sparse approximation of the inverse of a sparse matrix

**2**

**0**answers

### Can one optimize the probability that an identity is satisfied until the probability is $1$?

**4**

**1**answer

### complexity of bounded knapsack with spoilage

**7**

**1**answer

### Counting spanning trees of a planar graph

**0**

**1**answer

### Efficient isomorphic subgraph matching with similarity scores

**2**

**1**answer

### The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero

**0**

**0**answers

### A name for algorithms that perform well in an asymptotic sense, when inputs are random

**2**

**1**answer

### Bounds on the positive roots of a bivariate polynomial

**2**

**2**answers

### Fast Algorithms for sum of independent random variables

**1**

**1**answer

### Removing the minimum number of edges to make a graph triangle-free (using set cover)

**1**

**2**answers

### A variation of longest paths in directed acyclic graph

**8**

**6**answers

### How to approximate a solution to a matrix equation? [closed]

**10**

**3**answers

### Approximate volume computation and lattice point enumeration - hardness

**1**

**0**answers

### Heuristics for this “subset” traveling salesman problem

**2**

**0**answers

### Is there an algorithm for numerical approximation of (naive) period integrals

**1**

**0**answers