# Tagged Questions

**1**

vote

**1**answer

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

**1**

vote

**1**answer

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

**0**

votes

**1**answer

138 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

**2**answers

166 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

**1**answer

191 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

**1**answer

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

**0**

votes

**1**answer

200 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

**1**answer

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

**1**

vote

**0**answers

131 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

**1**answer

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

**0**

votes

**2**answers

236 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?

**1**

vote

**0**answers

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

**4**

votes

**1**answer

551 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

**2**answers

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

**1**

vote

**1**answer

211 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

**2**answers

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

**3**

votes

**0**answers

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

**5**

votes

**2**answers

511 views

### Runge-Kutta method with c<1

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