Questions tagged [approximation]
The approximation tag has no usage guidance.
58
questions
1
vote
0
answers
67
views
How to enforce convexity?
I have a problem for which the solution is known to be a convex $f:[a,b]\times[c,d] \rightarrow \mathbb{R}$ over some rectangular domain ($a<b$ and $c<d$). There are many situations (e.g. ...
- 111
0
votes
0
answers
115
views
Approximate inclusion-Exclusion?
I am trying to understand or find literature on the following problem of approximate inclusion exclusion.
Let $S:=\{A_i\}_{i=1}^{m}$ be a set of $m$ sets. Every intersection of $k$ elements in $S$ ...
- 706
1
vote
1
answer
253
views
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia:
The polynomial-time approximation algorithm for Max-Cut with the best
known ...
- 173
1
vote
1
answer
64
views
How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$
Consider a bimatrix game problem with matrix $A$ and $B$. The definition of the value $v = [v_1, v_2]$ of the Nash equilibrium $(x, y)$ are as follows,
$$v_1 = x^TAy,$$
$$v_2 = x^TBy.$$
The situation ...
- 141
0
votes
1
answer
62
views
Set cover where consecutive sets differ by at most one item [closed]
First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of ...
- 230
3
votes
1
answer
336
views
Fastest approximate triangle counting algorithms in dense graphs
One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the ...
- 610
4
votes
0
answers
101
views
Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm
I know the canonical way to show APX-Complete is to give an L-reduction from an already-known APX-complete problem. If I have used gap-preserving reduction to show a problem cannot be approximated ...
- 41
1
vote
0
answers
54
views
polytime approximability of directed multicut
Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be ...
- 21
10
votes
1
answer
586
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
0
votes
1
answer
93
views
Optimization problems with same optimal value, but different approximation behavior
Context: related to this answer.
I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense ...
- 1,633
5
votes
1
answer
573
views
If NP in BPP then NP equals RP
I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links:
https://cs.stackexchange.com/q/80509
http://www.inf.ed.ac.uk/teaching/...
- 1,217
4
votes
1
answer
964
views
Is an algorithm with an approximation factor of 4000 useful?
A paper published in SODA this year (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds.
To my surprise, when reading the ...
- 185
5
votes
0
answers
229
views
Martingale exit arguments for gradient Langevin dynamics
I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high ...
- 1,443
6
votes
1
answer
79
views
NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family
I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following:
There is a value $\...
- 1,424
0
votes
1
answer
104
views
Bi-criteria combinatorial approximation algorithms for min k-vertex cover
Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized.
It is easy to ...
- 111
3
votes
1
answer
269
views
Examples of nontrivial non-discriminatory functions
I am reading Cybenko's "Approximation by Superpositions of a Sigmoidal Function".
The paper defines a discriminatory function as:
$\sigma$ is discriminatory if for a measure $\mu$,
\begin{align}
\int ...
- 63
6
votes
0
answers
297
views
How hard is APPROXIMATE-#SAT?
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.
It is also suspected (somewhat less widely) that even deciding SAT should ...
- 203
1
vote
1
answer
177
views
How good of an approximate 2-coloring can you get of the halved cube graph?
We say that a 2-coloring $col : V_G \rightarrow \{0, 1\}$ of a graph $G$ is $\epsilon$-approximate if $Pr_{(w, v) \in E_G}(col(w) \neq col(v)) \geq \epsilon$. For every $n$, what is the maximum $\...
- 1,562
1
vote
1
answer
645
views
Approximately counting paths and cycles in a graph
Counting cycles, and paths in graphs is a hard problem, see questions here, and related question for cycles for a given length $k$, here. The question is about the approximability of these graph ...
- 1,081
1
vote
0
answers
133
views
Does the NP-hardness of finding any valid solution imply NPO-hardness?
Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as ...
- 373
7
votes
0
answers
177
views
Universal approximation theorem of second order
The universal approximation theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem)
informally states that up to several conditions, any function can be approximated by a shallow ...
- 181
7
votes
1
answer
668
views
Why isn't the Charikar algorithm for finding the densest subgraph optimal?
I read about the algorithm in
Greedy Approximation Algorithms for Finding
Dense Components in a Graph by
Moses Charikar,
and I tried to find an instance/graph where the algorithm returns a different ...
- 93
3
votes
0
answers
143
views
Approximation class of finding decision trees with minimal depth
We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i? $" for some $i$, taking the left branch means "yes", ...
- 373
2
votes
1
answer
516
views
Is there any known Poly-APX-complete minimimization problem?
All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (...
- 373
2
votes
0
answers
225
views
Proof of a (simple) lemma by Aaronson
I am reading this article, and I need help with an apparently obvious proof.
The lemma (on page 5), that I want to know the proof of, is this: Let $p : \{0,1\}^N \rightarrow \mathbb{R}$ be a real ...
- 355
6
votes
0
answers
175
views
Lower bound for Yao's algorithm on general addition chains?
An addition chain of size $n$ for given integers $n_1,n_2\dots ,n_p$ is a sequence of integers $k_1,k_2\dots ,k_n$ such that
$k_1=1$,
for all $i$ $(2\le i\le m)$ we have $k_i=k_j+k_m$ for some $1\le ...
- 490
2
votes
0
answers
215
views
Approximating the Radius of a (Dense) Graph
For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius.
A $(1+\epsilon)$-approximating of APSP for a ...
- 230
3
votes
1
answer
310
views
Looking for approximation class between NPO and Exp-APX
I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) ...
- 373
1
vote
0
answers
122
views
Truthful posted-price mechanism with optimal efficiency (social welfare)
I am interested in mechanism design. In the paper On Profit-Maximizing Envy-free Pricing, SODA, 2005, the authors provided a truthful competitive posted-price mechanism with $4\log h$ guarantee of ...
- 11
-2
votes
1
answer
108
views
Proving hardness of approximation with reduction in terms of 1/$\epsilon$
I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 < \epsilon < 1$. The reduction is polynomial in $n$ (the size of the instance of the ...
- 87
3
votes
0
answers
97
views
Estimate smooth vector, from dot-product queries
I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$. I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$. I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^...
- 11.3k
0
votes
0
answers
147
views
Approximating liveness properties with safety properties
Given a finite alphabet set $\Sigma$, the set $\Sigma^{\omega}$ of infinite words over $\Sigma$ can be topologized with a metric $d: \Sigma^{\omega} \rightarrow \mathbb{R}$ such as:
$\forall w_1, w_2 ...
- 163
17
votes
1
answer
507
views
smallest circuit size using XOR gates
Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables.
The goal is to compute the minimum ...
0
votes
1
answer
111
views
Calculate sum of reciprocal rank in arbitrary large graph
For arbitrary graph of n node, can I approximate $\sum_{v\neq u}\frac{1}{Rank_u(v)^a\times Rank_v(u)^b}$ with $\sum_{v\neq u}\frac{1}{Rank_u(v)^{a+b}}$ or not when n is large enough? $a,b>0$, $...
- 13
1
vote
1
answer
232
views
Is there any research on approximation of reals with computable numbers
I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
- 127
1
vote
0
answers
117
views
Computing log of sum of positive integers
As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input ...
- 727
5
votes
0
answers
120
views
The distribution on the solution space induced by randomized rounding
Consider the Goemans-Williamson algorithm for the MAX-CUT problem.
It is known, that if $maxcut(G) \geq 1-\epsilon$, then
the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
- 1,224
0
votes
1
answer
175
views
Finding optimal subset for quadratic function
Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a set $S$ of ...
- 11
1
vote
0
answers
45
views
Bounding the cost of an approximation algorithm when subtraction involve [closed]
Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound $\...
- 11
0
votes
0
answers
107
views
How can I show that zero-one programming is not in APX?
How can I show that zero-one programming is not in APX?
Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the
zero-one programming problem to Vertex Cover and show that ...
0
votes
0
answers
273
views
Calculating exact/approximate solution to a formula
Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$.
Consider ...
- 749
3
votes
0
answers
70
views
Do there exist "odd times" cover problems and what do we know about their approximability?
I am currently investigating a problem which can be formulated as a cover problem, in which real intervals have to be covered an odd number of times by integers.
My question is just, if anybody has ...
- 306
6
votes
1
answer
196
views
Minimize makespan on identical machines when jobs are vectors
Given are $n$ $d$-dimensional vectors and $m$ machines where $d$ need not be fixed. The objective is to minimize the makespan i.e., assign the vectors to machines such that the maximum of the ...
- 61
4
votes
2
answers
1k
views
Greedy MAX SAT approximation ratio
Consider a naive MAX SAT approximation algorithm:
pick a literal $l$ which appears in maximum number of clauses
set the corresponding variable of $l$, such that all clauses containing $l$ are ...
- 57
0
votes
0
answers
68
views
Asymmetric metric TSP when many edges have equal costs in both directions
I would like to ask whether there exists a better approximation result on a special case of the ATSP metric instances: when cost(a,b)=cost(b,a) for $O(log(|E|)$ edges, or something close/related to ...
- 47
7
votes
1
answer
965
views
Approximating Max-Coverage when the elements need to be covered multiple times
In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. ...
- 213
4
votes
1
answer
1k
views
Max-cut equivalence with most likely assignment to an Ising model
Ising Model
$$
Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum_{ij \in E} \lambda_{ij} x_{ij} \right)
$$
In which $\lambda_{ij} \in \mathbb{R}$, and
$$
x_{ij} =
\begin{cases}
1 & x_i = ...
- 749
3
votes
1
answer
1k
views
Finding maximum number of disjoint set covers
Let $U = [1..n]$ be the universe of $n$ elements and $C$ be a collection of subsets of $U$, $C= S_1, \dots, S_m$, where $S_i \subset U$. Then the problem is to find as many partitions of $C$, such ...
- 31
3
votes
1
answer
177
views
n-approximable functions
I came across the following definition in a paper:
We can extend the notion of an $n$-c.e. [n-computably enumerable] set to a notion that measures the number of fluctuations of a function as folows: ...
- 459
4
votes
1
answer
319
views
Approximating Bipartite Vertex Cover
Is there any result on approximating a minimum (weighted) bipartite vertex cover? I'm interested in the problem that given a bipartite graph ( probably with weight on its vertex ), find a vertex cover ...
- 223