# Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

37 questions
Filter by
Sorted by
Tagged with
14k views

### Universal Approximation Theorem — Neural Networks

I posted this earlier on MSE, but it was suggested that here may be a better place to ask. Universal approximation theorem states that "the standard multilayer feed-forward network with a single ...
13k views

### Approximation algorithms for Metric TSP

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. Is anything known about finding approximation solutions in ...
4k views

### Max-cut with negative weight edges

Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find: $$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$ If the ...
2k views

### Is there a sensible notion of an approximation algorithm for an undecidable problem?

Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them. For example, the halting problem is undecidable, but practical progress can be ...
2k views

### Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "...
2k views

### Bounded-cardinality bounded-frequency set cover: hardness of approximation

Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets. Example: the case $k = 4$ ...
758 views

### Set Cover for Permutation Matrices

Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has ...
498 views

### Smoothed analysis of approximation algorithms

Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for ...
6k views

### The importance of Integrality Gap

I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
2k views

### Integrality gap and approximation ratio

When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of ...
1k views

### Compendium of the Best Approximation and Hardness Results for NP optimization problems

Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result? Based on the feedback, it seems that it is safe to assume there is not such a ...
1k views

### Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
516 views

### Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
392 views

### Good reference about approximate methods for solving logic problems

It is known that many logic problems (e.g. satisfiability problems of several modal logics) are not decidable. There are also many undecidable problems in algorithm theory, e.g. in combinatorial ...
6k views

### Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?

I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function. Is there any modification of gradient descent which allows to find absolute minimum (maximum),...
3k views

### Is there an online-algorithm to keep track of components in a changing undirected graph?

Problem I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected ...
4k views

### Any fast algorithm for minimum cost feedback arc set problem?

In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set. If each edge is associated with a weight $w$, the minimum cost ...
688 views

### A Multi-cut Problem

I'm looking for a name or any references to this problem. Given a weighted graph $G = (V, E, w)$ find a partition of the vertices into up to $n = |V|$ sets $S_1,\ldots,S_n$ so as to maximize the ...
444 views

### Partitioning a segmented stick

Problem : We are given a stick partitioned into n - equal parts. Each of these parts has a weight, let's say x. Number of times x appears as weight of some part is guaranteed to be even. For ...
346 views

### Questions about computing matrix rigidity

Matrix rigidity was introduced by Valiant in 1977: The rigidity $Rig_M(r)$ of boolean matrix $M$ over GF(2) is the smallest number of entries of $M$ that must be changed in order to reduce its rank ...
1k views