#StackBounty: #machine-learning #neural-networks #optimization #approximation #polynomial Quantifying the universal approximation theorem

Bounty: 100

Let $mgeq 1$ be an integer and $Fin mathbb{R}[x_1, dots, x_m]$ be a polynomial. I want to approximate $F$ on the unit hypercube $[0, 1]^m$ by a (possibly multilayer) feedforward neural network. The activation function is $mathrm{tanh}$ for all the connections.

Let $varepsilon>0$ be a real number. If I want the approximation to deviate from $F$ by less than $varepsilon$ in the $L^2$ norm what is the smallest possible number of non-zero weights?

It is kind of stupid to approximate a function that is known to be polynomial by a neural network but I just wanted to get more quantitative insight into the universal approximation theorem (and polynomials seem to be the most accessible class of functions).


Get this bounty!!!

#StackBounty: #algorithms #optimization #approximation #scheduling #intervals 2D interval scheduling problem

Bounty: 50

Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) ${(w_i, h_i, x_i) mid i in {0, ldots, n – 1}}$, as well as a bound $(y_mathrm{min}, y_mathrm{max})$ on the valid y-positions. These rectangles must have integer-valued coordinates for their vertices. Is there an efficient (e.g.: $O(n^3)$) approximation algorithm that gives a sequence ${y_0, ldots, y_{n – 1}}$ of y-positions such that the number of overlaps between any two rectangles (i.e.: edges in the overlap graph) is minimized (and hopefully zero)?

Note that if $y_mathrm{max} = 10$ and $h_k = 3$, then $y_k = 9$ would be invalid, since the top edge would be at $12$ which is more than $10$.


Get this bounty!!!

#StackBounty: #algorithms #graphs #approximation #vertex-cover Vertex cover of bipartite graph

Bounty: 50

A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
A minimum vertex cover is a vertex cover with minimal cardinality.

https://codeforces.com/blog/entry/63164

Consider a set of all minimum vertex covers of a given bipartite graph,
our task is to divide all vertices of the graph into three sets.

A vertex is in set

  • N (“Never”) if there is no minimum vertex cover containing this vertex.
  • A (“Always”) if it is a part of every minimum vertex cover of the given graph.
  • E (“Exists”), otherwise.

I don’t understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

This is the graph I have ($2K_2$) two edges in the maximum matching:

2K_2

For the first edge I took left vertex in the cover
$x_1=0$ (according to the blog in the link)
for the second edge I took right vertex in the cover $x_2=1$.

Questions:

  1. How final 2-sat will be true?
  2. Can anyone explain what will be the relation between x1 and x2 ?


Get this bounty!!!