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

11 questions
Filter by
Sorted by
Tagged with
279 views

### Confusion with practically implementing rational approximations

Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let ...
• 16.3k
417 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 ...
• 555
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$ ...
336 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 ...
• 3,511
435 views

• 521
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 ...
• 1,158
601 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 ...
• 453
121 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 ...
• 79.9k
124 views

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

I wonder how well one can obtain algebraic structures that satisfy interesting algebraic identities by simply slowly modifying those algebraic structures until they satisfy the required identities. I ...
• 23.2k
Definition Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...