Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
46
questions
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
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
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
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
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
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
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
12
votes
1
answer
559
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 ...
- 367
10
votes
2
answers
2k
views
Maximizing sum edge weights
I am wondering if the following problem has a name, or any results related to it.
Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,...
- 9,850
4
votes
1
answer
427
views
Approximation algorithms for min vector subset-sum over GF(2)
In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum.
Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to ...
- 1,318
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
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 ...
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, ...
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
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
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
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
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
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
11
votes
2
answers
5k
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 ...
- 161
10
votes
1
answer
610
views
Is the following graph optimization problem approximable within a constant factor?
Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$.
For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
- 563
9
votes
0
answers
306
views
Additive error in counting the number of 1's in a sliding window?
The setting is as follows:
We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
- 9,438
9
votes
2
answers
550
views
Approximating #P-hard problems
Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there ...
- 165
8
votes
2
answers
1k
views
Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed
The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the ...
- 1,468
8
votes
1
answer
2k
views
How bad can the greedy coloring (list color) for the c-chromatic number of graph be?
c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-...
- 1,443
7
votes
3
answers
2k
views
A simple approximation algorithm for the TSP
Consider the following extremely simple approximation algorithm for the TSP.
Input: A complete weighted graph $G=(V,E).$
Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$
While there ...
- 348
7
votes
1
answer
781
views
Approximating transitive reduction of a transitive closure of a dag
Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the ...
- 696
7
votes
1
answer
927
views
Ordering of a DAG minimizing some definition of cost
Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k>i: (v_j,v_k)\in A\...
- 251
6
votes
1
answer
313
views
Approximation schemes for P-complete problems?
What work has been done on approximation schemes for $\mathsf{P}$-complete optimization problems? Would the desired approximation algorithms here be "fully log-space approximation schemes" or "fully $\...
- 2,281
5
votes
3
answers
639
views
bin packing with overlapping objects
I have $N$ bins with capacity $M$ and $k$ objects with size $s_i$. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object ...
- 199
5
votes
2
answers
383
views
A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching
The question is asked first at here. It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness.
Problem: Given a graph $G(V,E)$, ...
- 1,443
5
votes
3
answers
477
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 ...
Prof. Cees Duke
4
votes
0
answers
571
views
Hardness of Approximation for minimum path cover in an undirected graph?
Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
- 53
4
votes
0
answers
117
views
Approximating Front Size of Asymmetric Matrices
The front size of a matrix $A$ is the largest number of non-zeros below the diagonal in any column of its Cholesky factor. If $A$ is symmetric then the minimum front size of $A$ is equal to the ...
- 10.6k
3
votes
2
answers
567
views
Finding a set which dominates the Minimum Dominating Set
Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.
The dominating set problem is NP-hard, but I am considering ...
- 607
3
votes
2
answers
194
views
Minimum relevant variables in linear system - additive approximation
In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.:
$$ A x = b $$
and the goal is to find a solution $x$ with as few nonzero variables as ...
- 2,086
3
votes
0
answers
153
views
Exactly solvable but non-trivial integrality gap
Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap?
Note: Maximum matching doesn't qualify because I ...
- 6,970
3
votes
0
answers
161
views
Hessian of non differentiable convex function
The motivation of the question is the following:
Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\...
- 265
2
votes
1
answer
136
views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
user53330
2
votes
0
answers
90
views
Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?
In online-setting, we usually allow exponential time to think and come up with a strategy. On the other hand, in offline-setting, we might care about solving a particular problem optimally, or as good ...
- 21
1
vote
2
answers
3k
views
Is the current best approximation ratio for Vertex Cover problem also a lower bound?
In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we ...
- 193
1
vote
1
answer
237
views
The Complexity of Multi-Objective Optimization
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
- 67
1
vote
1
answer
651
views
The Goemans-Williamson algorithm in the $SOS$ framework
If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...
- 271
1
vote
1
answer
393
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 ...
- 11k
1
vote
0
answers
295
views
Generalization Issues with Practical Suggestions from Universal Approximation Theorem with Neural Networks
After having read matus's beautiful answer in this thread explaining (among other things) Cybenko's proof of the Universal Approximation Theorem for Neural Networks, I wonder: if we use a piecewise ...
