# Tagged Questions

An approximation algorithm is an algorithm that finds an approximate solution to a (typically NP-hard) problem. The quality of the algorithm is measured by how close to the actual optimum it performs. For example, it is a constant factor approximation algorithm if it always outputs a solution that ...

67 views

### Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\{1,\ldots,m\}$, I want to maximize the quantity \sum_{k=1}...
181 views

### Optimize a convex hull on a 2D histogram so the selected points match a target shape

I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I ...
1k views

### Removing cycles from an undirected connected bipartite graph in a special manner

Consider an undirected connected bipartite graph (with cycles) $G = (V_1,V_2,E)$, where $V_1,V_2$ are the two node sets and $E$ is the set of edges connecting nodes in $V_1$ to those in $V_2$. We ...
134 views

### Near-linear Function aproximation

Hi, I have a growing, near-linear function, that has some "noise" in its linearity. Is there any solution, how to approximate this function ? I tried Neural Network, but ist not best... Function ...
382 views

### Enlcosing a set of ellipses within one ellipse

Hello, Is there an algorithm that takes in a set of ellipses and gives back and ellipse that encloses the set?
1k views

### When we use Bernstein polynomials in application

When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", "Simple ...
136 views

### A.G. Vitushkin's “Easily representable families of functions” - can it be generalized?

Background In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies ...
559 views

### Set Cover:Greedy vs LP

Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks
247 views

70 views

### An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points (...
238 views

366 views

### Approximation of conformal mapping as a sum of elementary conformal mappings

Hi, I would like to approximate any 2d conformal mapping, as a sum of elementary conformal mappings. So I would have some basis, a conformal mapping with some parameters, and by adding several ones ...
873 views

### Approximating e with 2s and 3s

How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to e as possible? For example: ...
8k views

### HOW TO Generate Equation of a Curve Given (x,y) pairs - algorithm? [closed]

Hi, How can I generate the equation of a curve that matches all arbitrarily given (x,y) pairs? I would like a polynomial of nth degree, where n does not matter, as long as the curve passes thru all ...
For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...
A standard greedy algorithm for solving the weighted set-cover problem can be proven to be a $\log(n)$ approximation. I have a variant of weighted set cover, and I came up with a greedy algorithm for ...