Questions tagged [approximation]

The tag has no usage guidance.

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
14
votes
0answers
348 views

Finding all-pairs anti-distance

Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem. Let $G=(V,E)$ ...
7
votes
0answers
167 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 ...
6
votes
0answers
206 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 ...
6
votes
0answers
153 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 ...
6
votes
0answers
838 views

k-CNF ←→ k-DNF conversion to minimize errors

the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ...
5
votes
0answers
216 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 ...
5
votes
0answers
115 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}$...
3
votes
0answers
122 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", ...
3
votes
0answers
64 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}^...
3
votes
0answers
61 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 ...
3
votes
0answers
265 views

Maximizing a convex function where the objective function is separable but the search space is not

The problem statement is Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$ Does this kind of problem structure allow one to use specific strategies to solve the ...
2
votes
0answers
189 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 ...
2
votes
0answers
170 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 ...
1
vote
0answers
99 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 ...
1
vote
0answers
113 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 ...
1
vote
0answers
103 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 ...
0
votes
0answers
103 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 ...
0
votes
0answers
81 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
0answers
201 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 ...
0
votes
0answers
59 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 ...