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 ...

learn more… | top users | synonyms

1
vote
0answers
44 views

Asymptotic determinant of $2\times 2$ Toeplitz matrix

The problem that I am dealing with is to compute the determinant of a $2\times 2$ Toeplitz matrix[1] (in general I would like to generalize to a more general case, but let's consider the easiest case ...
0
votes
0answers
29 views

Matrix Completion: Clearing Step

I am trying to implement Keshavan, Montanari and Oh (2009) algorithm for Matrix Completion. It consists of three steps: 1) Trimming which nulls some rows and columns to make the high singular values ...
17
votes
2answers
427 views

“Fractally self-similar” numbers

This is another question about visualization of Ford circles, the previous one being Confusion with practically implementing rational approximations. Here is an output of zooming into Ford circles at ...
10
votes
1answer
212 views

Confusion with practically implementing rational approximations

Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let ...
1
vote
0answers
23 views

Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph. I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...
3
votes
0answers
88 views

Group Travel Salesman Problem

For the following Group Traveling Salesman problem, I'd like to know if there exists some poly-time approximation algorithm with constant approximation factor. Group TSP is defined as follows: Take a ...
7
votes
1answer
257 views

State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are ...
3
votes
0answers
153 views

Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...
3
votes
0answers
33 views

Solving a Certain Constrained Isoperimetric Approximation-Problem

This question is related to my question Differential Geometric Aspects of Rubber Bands, where I asked for a mathematical model of contracting rubber bands. In contrast to my former question, the ...
5
votes
0answers
81 views

Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.) For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...
1
vote
0answers
61 views

FPTAS for approximating the permanent of a matrix

My question concerns approximating permanent of an $n$-by-$n$ matrix. Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...
3
votes
0answers
143 views

Estimating the growth rate of nondeterministic finite automata

Given a nondeterministic finite automaton $\mathcal{A}$ (or a regular expression, or a regular grammar), can we efficiently compute the number $|L_k(\mathcal{A})|$ of accepted words of length $k$? ...
7
votes
0answers
135 views

Nearest Point to a real algebraic set

Suppose I have a compact bounded real algebraic (eventually: or analytic or semialgebraic or semianalytic set) $V$ in $\mathbb R^3$ and a point $x\in\mathbb R^3$ not in $V$. How much do we know about ...
2
votes
3answers
222 views

Determining Roots of a Polynomial with Interval Estimates of Coefficients

Let $f$ be a monic univariate polynomial with real coefficients: $$f_A(x) = x^n + a_{n-1}x^{n-1} + ... + a_{0}$$ The values of $A=(a_{n-1},...,a_0)$ are unknown, but are estimated as ...
1
vote
1answer
59 views

Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ ...
3
votes
3answers
738 views

Construct the best piece-wise linear continuous function fitting given curve

How to construct the optimal piece-wise linear continuous function fitting given curve and given number of knots (optimal knots positions also must be determined by this method)?
1
vote
1answer
97 views

Computing row-sum scaled unsigned Stirling nos. of the 1st kind

As the title suggests, I would like to compute probability vectors with elements proportional to (unsigned) Stirling numbers of the first kind by row. For easy reference, here is the Wiki page. For ...
6
votes
2answers
245 views

Approximating the action of the U(N) exponential map

Let's say that I have a curve in $\mathbb{C}^N$ given by the action of the unitary group: $$x(t) = e^{Ht}x_0,~ H \in \mathfrak{u}(N),~ ||x_0||=1$$ Here, $H$ is an NxN skew-Hermitian matrix (for very ...
0
votes
0answers
34 views

Inapproximability of logarithmic factor of independent set

The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to ...
1
vote
1answer
60 views

How to select a subset of points from a universal to minimize the distance from outside to inside?

Here is the detailed problem. I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as $$ ...
1
vote
1answer
59 views

Heuristic for choosing n-vectors from n-sets

my given problem is: choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
3
votes
2answers
258 views

Approximation of curves

When constructing minimax (sup-norm) polynomial approximations of real-valued functions, well-known results say (roughly speaking) that optimal solutions are characterized by the fact that they have ...
1
vote
2answers
181 views

Bivariate Function Approximation

I am working on a nonlinear control design and having difficulty in finding approximation of bivariate functions. Are there papers or methods discussing the following question: For any bivariate ...
2
votes
1answer
82 views

Convergence of Symmetric Iterative Proportional Fitting

Let $A$ denote a symmetric matrix of non-negative entries, whose rows (and columns) sum up to the all-positive vector $d := A\mathbf{1}$ with $\mathbf{1}$ the all-one-vector. Denote $D := diag(d)$ by ...
0
votes
1answer
249 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
4
votes
1answer
91 views

Norms of B-spline coefficients

In Shumaker's book (Spline Functions: Basic Theory), we know that the $l^\infty$-norm of B-spline coefficients is bounded above and below by the $L^\infty$-norm of the spline itself. Are there similar ...
1
vote
1answer
257 views

Approximation of a given function by rational functions

Given a function $1/\sqrt{x^2 -k^2}$ where k is a constant with a small imaginary part, how do you go about constructing a rational approximation? I am interested in the L_p (p=2 or $\infty$) norm of ...
3
votes
0answers
294 views

Tiling a rectangle with weighted cells (min-max problem)

I have been struggling with a research problem. The problem can be formalized as follows: Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ ...
3
votes
2answers
2k views

Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix? The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
4
votes
2answers
308 views

Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is: ...
3
votes
1answer
411 views

Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules. Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...
1
vote
1answer
146 views

What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem? Beltway Reconstruction Problem: Assume there is a set of ...
4
votes
0answers
189 views

envelope function for a linear combination of gaussian distributions

Given a distribution $F$ defined as a linear combination of Gaussian distributions: $F = \sum_{i=1}^n C_i*N(\mu_i,\sigma_i)$ with $\sum_{i=1}^n C_i = 1$ I want to find a Gaussian function $Q = ...
3
votes
0answers
65 views

Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
3
votes
3answers
740 views

iteratively (approximately) solving a sum of exponentials

I would iteratively have to solve the following equation at iteration $n$: $C = \sum_{1 \leq i \leq n}{e^{\frac{x_i}{T}}x_i}$ for $T$. Each iteration $i$ an unknown $x_i$ will be observed and $C$ is ...
0
votes
1answer
336 views

Giving a general term of a recursive function, and upper bound for it

Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$. Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise Let ...
3
votes
1answer
160 views

Using Fourier Transform to speed up calculation of forces following an inverse square law

Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...
0
votes
0answers
65 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 \begin{equation} ...
1
vote
0answers
170 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 ...
2
votes
1answer
950 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 ...
1
vote
2answers
132 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 ...
0
votes
2answers
358 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?
4
votes
4answers
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 ...
2
votes
0answers
135 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 ...
0
votes
0answers
160 views

Pure greedy algorithm

I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that ...
3
votes
2answers
363 views

How to check numerical precision of my computation of Stieltjes-constants?

In a thread in MSE I proposed an older routine of mine for the efficient computation of coefficients; I use a very similar routine for the quick&dirty computation of the Stieltjes-constants. ...
5
votes
3answers
2k views

How to make an approximation of path with polynom P(x,y)=0?

Hi. Imagine that a user draws on the canvas any path. I want to approximate this path with a path $P(x,y)=0$ where $P(x,y)$ - is unknown polynom. May be somebody can suggest an appropriate algorithm? ...
1
vote
0answers
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 ...
3
votes
0answers
238 views

Place n telescopes on a sphere in R^d to see the whole sky

Where would one put $n$ telescopes on the surface of the earth to see the whole sky as well as possible ? Use the cosine metric to define how well we can see in direction $x$: $ \qquad \text{cansee}( ...
8
votes
1answer
511 views

How to evaluate binomial coefficients efficiently and as correctly as possible?

This question is more precisely about evaluation with a computer, of a binomial coefficient of the form $ \binom{x}{m}$ where $x$ is a real number and $m$ a rational integer. The reason why I ask is ...