The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
171 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 ...
8
votes
0answers
422 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 ...
7
votes
0answers
124 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 ...
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 ...
4
votes
0answers
149 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
245 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
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}( ...
3
votes
0answers
196 views

Algorithm for testing satisfiable fraction of linear equations mod 2

Hello Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation ...
2
votes
0answers
61 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$? ...
2
votes
0answers
66 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 ...
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 ...
2
votes
0answers
124 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 ...
1
vote
0answers
48 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 ...
1
vote
0answers
57 views

Mixture with varying concentrations

Let $(\Omega ,\mathcal F, \mathbb P)$ be a probability space and suppose $$\mathbb P(X \in A) = H(A) = \prod _{i=1}^m H_i(A),\quad \forall A\in \mathcal F$$ be a distribution of a random vector $X = ...
1
vote
0answers
147 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 ...
1
vote
0answers
68 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 ...
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 ...
1
vote
0answers
457 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]$) ...
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
34 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 ...
0
votes
0answers
60 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} ...
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 ...
0
votes
0answers
110 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 ...
0
votes
0answers
317 views

Approximate a piecewise linear path by a path with bounded curvature

I have a piecewise linear path in two dimensions (with finitely many pieces). I would like to approximate it by a curve whose radius of curvature is bounded away from 0 (i.e. I specify the bound a ...