Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
513
questions
49
votes
8
answers
9k
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 ...
- 21.5k
49
votes
3
answers
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 ...
- 7,465
46
votes
4
answers
14k
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 ...
- 2,247
39
votes
9
answers
4k
views
Optimal greedy algorithms for NP-hard problems
Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
- 10.6k
37
votes
3
answers
5k
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 ...
- 9,850
36
votes
1
answer
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 "...
- 4,902
35
votes
11
answers
2k
views
Approximation algorithms for problems in P
One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for ...
- 951
29
votes
4
answers
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$ ...
- 11.5k
29
votes
4
answers
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 ...
27
votes
4
answers
1k
views
Quantum approximation algorithms
It is generally considered unlikely that quantum computers will be able to solve NP-complete problems efficiently. In the classical case one approach to tackle such problems is to use approximation ...
- 371
27
votes
3
answers
988
views
When is relaxed counting hard?
Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
- 4,681
25
votes
2
answers
15k
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 ...
- 493
24
votes
5
answers
3k
views
Approximation algorithms for Maximum Independent Set on special classes of graphs
We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better ...
- 1,591
22
votes
5
answers
2k
views
Theoretical Applications for Approximation Algorithms
Lately I've started looking into approximation algorithms for NP-hard problems and I was wondering about the theoretical reasons for studying them. (The question is not meant to be inflammatory - I'm ...
- 229
22
votes
2
answers
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, ...
22
votes
3
answers
622
views
Educational Source or Survey on Analysis of Semidefinite Program?
When designing approximation algorithms one sometimes solves a semidefinite program followed by a rounding step. An often used example to illustrate this is Max-Cut. (See e.g. Approximation Algorithms ...
- 436
21
votes
1
answer
914
views
Approximate 1d TSP with linear comparisons?
The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way ...
- 50.9k
20
votes
1
answer
428
views
What are the best possible time/error tradeoffs for approximate solution of linear programs?
For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity ...
- 1,874
19
votes
3
answers
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 ...
- 1,200
17
votes
3
answers
540
views
Is there a constant factor approximation algorithm for 2D rectangle coloring problem?
The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
- 193
17
votes
2
answers
849
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 ...
- 173
17
votes
3
answers
522
views
Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?
There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an ...
- 4,215
17
votes
1
answer
617
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 ...
- 1,099
17
votes
0
answers
780
views
Practically Good Algorithms of a Very Low Computational Complexity Class
I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties:
1) Solving the ...
- 6,013
16
votes
2
answers
554
views
Characterization of problems for which sublinear time algorithms exist
I was wondering if problems for which sublinear time (in the input size) algorithms exist can be characterized as possessing specific properties. This includes sublinear time (e.g. property testing, ...
- 2,216
16
votes
1
answer
538
views
Can we approximate the number of words accepted by an NFA?
Let $M$ be an acyclic NFA.
Since $M$ is acyclic, $L(M)$ is finite.
In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete.
The second ...
- 9,438
15
votes
2
answers
1k
views
What is known about this TSP variant?
This question was previously posted to Computer Science Stack Exchange here.
Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've ...
- 253
15
votes
3
answers
4k
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 ...
- 351
15
votes
2
answers
347
views
Approximation in subexponental time
There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete ...
- 12.8k
15
votes
1
answer
493
views
Imperfect subgraph isomorphism
Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges ...
- 8,896
15
votes
1
answer
463
views
Graph decompositions for combining "local" functions of vertex labelings
Suppose we want to find
$$\sum_x \prod_{ij \in E} f(x_i,x_j)$$
or
$$\max_x \prod_{ij \in E} f(x_i,x_j)$$
Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...
- 4,681
15
votes
1
answer
623
views
Does PSPACE-completeness imply approximation hardness?
It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it?
Is this "tight"? (i.e., are there PSPACE-...
- 9,438
15
votes
1
answer
949
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
- 2,786
15
votes
0
answers
388
views
Complexity of approximating the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$
I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
- 3,950
14
votes
2
answers
755
views
Proof assistant usage in complexity theory research?
Considering the topics covered at a conference like STOC, are any algorithm or complexity researchers actively using COQ or Isabelle? If so, how are they using it in their research? I assume most ...
- 385
14
votes
1
answer
594
views
Why is the Greedy Conjecture so difficult?
I recently learned about the Greedy conjecture for the Shortest Superstring Problem.
In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ ...
- 475
14
votes
0
answers
614
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 1,953
14
votes
1
answer
343
views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(...
- 838
13
votes
5
answers
7k
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),...
- 233
13
votes
2
answers
1k
views
Relation between fixed parameter and approximation algorithm
Fixed parameter and approximation are totally different approaches to solve hard problems. They have different motivation. Approximation looks for faster result with approximate solution. Fixed ...
- 467
13
votes
2
answers
375
views
Strengthenings of submodularity
A set-function $f$ is monotone submodular if for all $A,B$,
$$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B). $$
A stronger property is
$$ \begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\...
- 14.3k
13
votes
1
answer
631
views
Is DAG subset sum approximable?
We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$.
The DAG subset sum problem (might exist under a ...
- 9,438
13
votes
2
answers
655
views
Estimating VC-Dimension
What is known about the following problem?
Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-...
- 9,850
13
votes
1
answer
427
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 ...
- 409
12
votes
3
answers
788
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 ...
- 9,850
12
votes
3
answers
586
views
What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?
What are the problems with the best known approximation ratio achieved by an algorithm returning a uniformly random solution?
I know one such example for permutation flow shop problem $F|perm|C_{max}...
- 4,215
12
votes
4
answers
836
views
Approximation algorithms used in exact algorithms
Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms.
However, constant factors are ignored in time complexity.
So I wonder if ...
- 1,261
12
votes
5
answers
571
views
Submodular functions: reference request
I would be very much interested in references to the theory of submodular functions (from basics to advanced).
In particular, I am studying approximations to hard optimization problems and I want to ...
- 664
12
votes
3
answers
2k
views
counting independent sets
What algorithms/mathematical techniques are available to exactly/approximately count number of independent sets?
Is/Are there a good reference/good references on this topic?
I am interested in ...
- 2,208
12
votes
2
answers
547
views
Approximate graph colouring with a promised upper bound on maximum independent set
In my job the following problem arises:
Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 ...
- 123