Tagged Questions

35 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  ...
26 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 ...
136 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 ...
165 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: ...
187 views

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 ...
135 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 ...
198 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 ...
144 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 ...
127 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 ...
349 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 ...
235 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?
66 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 ...
549 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? ...
492 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 ...
210 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 ...
1k views

Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
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 ...
In trying to solve an ODE $y'=f(y,t)$ with a function f that is discontinuous at a subset (codim=1) of $\mathbb R^n$, I am looking for a Runge-Kutta ODE method whose stages do not evaluate $f(x,t)$ at ...