The approximation-algorithms tag has no wiki summary.
7
votes
0answers
120 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
136 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 ...
0
votes
1answer
37 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 \ ...
2
votes
3answers
210 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
70 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
233 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
29 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 ...
0
votes
0answers
53 views
Any software that can symmetrize input sets?
Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not.
Which software would you suggest for rigid transformations?
Thank you
0
votes
0answers
17 views
Estimating Missing Shortest-Path-Tree Distances from Point Coordinates
Problem:
given
a finite set of points $\mathcal{P}:=\lbrace p_i\in\mathbb{R}^2 \mid i\in \lbrace 0,...,n\rbrace\wedge i\neq j\Leftrightarrow p_i\neq p_j\rbrace$
a function ...
0
votes
0answers
33 views
Approximation with Predefined Topology of Niveau Sets
Problem
given are
a finite, connected, undirected and, cycle-free graph (i.e. a "tree") $T(V,E)$, of which one of the vertices (w.l.o.g. $v_0$) is defined to be the root.
a planar imbedding ...
1
vote
1answer
40 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
52 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 ...
4
votes
2answers
234 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
1answer
138 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
0answers
62 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
166 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 ...
2
votes
0answers
42 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
223 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 ...
-1
votes
1answer
96 views
Recursion equation convergence to sqrt [closed]
I'm new here. I have a recursion equation
$$
a[n] = \frac{n \cdot a[n-1]}{n+a[n-1]} + k
$$
$$
a[1] = 1
$$
$$
k \in \mathbb{R}, k > 0
$$
and from computing and ploting graphs I found that it can ...
3
votes
0answers
237 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
945 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
197 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
284 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
139 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
143 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 = ...
2
votes
0answers
55 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
582 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
221 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
149 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
59 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
141 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
473 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
122 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
257 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
944 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
122 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
155 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
338 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.
...
3
votes
1answer
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
67 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
236 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
0answers
415 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 ...
1
vote
0answers
227 views
Multiobjective semidefinite programming
Let $C$ be size $n \times n^{2}$.
Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.
There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$.
$B$ is ...
4
votes
1answer
571 views
Lovász $\delta$ condition for LLL Algorithm
http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
What is the importance of the $\delta$ parameter for LLL bases called Lovász condition?
...
5
votes
2answers
532 views
Getting started: combinatorial optimization for computer scientists
I have a background in computer science and I am starting to work on some problems those are basically combinatorial optimization problems.
I have good knowleges of graphs, *-flow algorithms and so ...
0
votes
0answers
109 views
sparsest cut always has solution
Hi!
How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.
Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
1
vote
1answer
219 views
Approximate Set Cover Problem by Rounding
Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets ...
1
vote
0answers
453 views
Representing vertices of a cube using linear combination of tensor product of smaller cubes
Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.
Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)
...
2
votes
2answers
511 views
biggest cube problem (given set of bricks)
Input: set of bricks, each one is made of 1x1x1 cubes glued together face to face, like tetris pieces.
Problem: find the way of putting together those pieces to make a solid that contains biggest ...
5
votes
0answers
235 views
Any approximation algorithms for self-avoiding walks?
I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
