# Questions tagged [approximation]

The tag has no usage guidance.

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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)$ ...
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 ...
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 ...
153 views

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 ...
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 ...
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 ...
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) . So we can focus on approximating the radius. A $(1+\epsilon)$-approximating of APSP for a ...
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 ...
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 ...
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 ...