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

162 questions
Filter by
Sorted by
Tagged with
19 views

• 745
62 views

### Approximate solution problem of rank-one modification matrix secular equation

In Golub's paper , page 327,the eigenvalues of a rank-one modification of a $n\times n$ symmetric matrix can be computed by findng the zeros of the secular equation \begin{equation*} w(\lambda_j)=...
• 43
1 vote
180 views

146 views

### A variation of Set Cover

Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...
79 views

### Lagrange's interpolating polynomial

Let $f:[a,b]\rightarrow R$ be a function that is not $C^{(n+1)}$ on $[a,b]$ but its $n$-th derivative is a Lipschitz function? How does the Lagrange's interpolating polynomial formula change? How does ...
• 1
37 views

### Approximation algorithm for non-infinite diameter of sparse directed graph

There are some good approximation algorithms that compute the diameter of a sparse directed graph, for example, this one. Consider a little variation of the definition of diameter: we rule out ...
• 1,410
16 views

### Is there any reference proving hardness of approximation results for Linear Integer Programming With restricted finite domain?

Given $m\times n$ matrix $A$ of integers and $m\times 1$ vector $b$ of integers, the problem of whether there exists an $n\times 1$ vector $x$ of integers, such that $Ax=b$ and $x\geq 0$?, is known to ...
182 views

• 5,047
1 vote