The algorithms tag has no wiki summary.

**1**

vote

**1**answer

216 views

### Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.
One of the respondents cited Professor David Speyer's Math ...

**1**

vote

**2**answers

707 views

### The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.
Preliminary: Mertens function and the ...

**2**

votes

**1**answer

409 views

### Does a product of matrices have eigenvalue 1

Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$.
For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an ...

**2**

votes

**1**answer

279 views

### An algorithm for checking if a nonlinear function f is always positive

Is there an algorithm to check if a given (possibly nonlinear) function f is always positive?
The idea that I currently have is to find the roots of the function (using newton-raphson algorithm or ...

**3**

votes

**3**answers

385 views

### How to find the minimum number of hyperplanes to define a convex hull?

I have the following problem:
I have a convex hull $\Omega$ defined by a set of n-dimensional hyperplanes $S = [(n_1,d_1), (n_2,d_2),...,(n_k,d_k)]$ such that a point $p \in \Omega$ if $n_i^T p \geq ...

**1**

vote

**0**answers

63 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

264 views

### Polyline Averaging

I'm trying to find a method that can take a collection of polylines, each described by a list of connected points on a plane, and find an "average" path through them. The input lines do not loop.
...

**4**

votes

**2**answers

179 views

### Extension of conjugacy problem

Let $F = \langle a,b \rangle$ be a non-abelian free group.
Question: Is there an algorithm that takes as input $x,y,z \in F$ and answers the question whether $x$ is a product of conjugates of $y$ ...

**4**

votes

**0**answers

278 views

### Matching a binary matrix

Given a MxN 0-1 matrix D, with the property that
both M and N are odd numbers
its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).
How do we find M ...

**9**

votes

**3**answers

836 views

### Mertens' function in time $O(\sqrt x)$

This MathOverflow question seems to indicate that the state of the art in computing
$$
M(x)=\sum_{n\le x}\mu(n)
$$
takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...

**6**

votes

**0**answers

418 views

### Is Logical Min-Cut Problem, NP-Complete?

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...

**2**

votes

**1**answer

430 views

### #P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...

**2**

votes

**1**answer

465 views

### practical algorithm for constrained triangulation in two dimensions?

I'm looking for an algorithm that is easy to implement in practice (resulting in small amount of code), preferably incremental. As far as I know, the biggest problem with incremental constrained ...

**2**

votes

**1**answer

102 views

### Do you know a shortes path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with ...

**2**

votes

**1**answer

163 views

### Covering set problem

All the references I can find to Covering Set appear to be algorithmic. Is there are any reference for the simple existential question ---
Suppose we have $k$ sets $X_1,…,X_k$ which are subsets of a ...

**1**

vote

**0**answers

159 views

### Finding the smallest subset whose intersection is empty

Given a (finite) set $S$ of (finite) sets such that $\bigcap S = \emptyset$, how can I find all the smallest subsets $S' \subseteq S$ such that $\bigcap S' = \emptyset$?
Of course, I could just ...

**4**

votes

**1**answer

191 views

### Consistency of systems of inequalities involving only differences

I have a very large number (670 billion) of systems of inequalities of the form:
$C_1 - C_2 < C_4 - C_3 \wedge C_3 - C_2 < C_5 - C_3 \wedge ...$
where the $C_i > 0$. Ie. each system of ...

**1**

vote

**1**answer

611 views

### Multiple disjoint subset sum problem

Given two sets of nonnegative integer numbers:
$X = {x_1, x_2, ... x_n}$
$Y = {y_1, y_2, ... y_m}$
Need to find partition of $X$ on $m$ disjoint subsets, such as sum of elements in $i$-th subset ...

**12**

votes

**0**answers

293 views

### Best known constant for parallel sorting

I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because ...

**12**

votes

**3**answers

454 views

### Recognizing the 4-sphere and the Adjan--Rabin theorem

The problem of recognizing the standard $S^n$ is the following:
Given some simplicial complex $M$ with rational vertices representing a closed manifold,
can one decide (in finite time) if $M$ is ...

**5**

votes

**1**answer

298 views

### Fastest algorithm to compute (a^(2^N))%m?

Hi.
There are well-known algorithms for cryptography to compute modular exponentiation $a^b\%c$ (like Right-to-left binary method here : http://en.wikipedia.org/wiki/Modular_exponentiation).
But do ...

**9**

votes

**1**answer

867 views

### Groebner basis for Sudoku

I'm trying to write a program that solves sudoku's using a Groebner basis.
I introduced 81 variables $x_1$ to $x_{81}$, this is a linearisation of the sudoku board.
The space of valid sudokus is ...

**6**

votes

**2**answers

490 views

### Two groups acting on a set.

Suppose we are given a set S of points on which two different groups G and G' (given by sets of generating permutations) act. Is there an efficient algorithm for finding generators the largest pair ...

**1**

vote

**1**answer

185 views

### Shortest absolute value of path in graph

Suppose we have a weighted, acyclic digraph, with positive and negative edge weights.
Is there an algorithm that determines whether there is a path of weight zero between vertices A and B? The ...

**8**

votes

**0**answers

359 views

### Shortest path in Cayley graphs

The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...

**1**

vote

**0**answers

272 views

### Determine the next number in the sequence

This problem originates from a programming interview problem. In that problem, we are asked to convert the array $[a_0, a_1, \cdots, a_{N-1}, b_0, b_1, \cdots, b_{N-1}, c_0, c_1, \cdots, c_{N-1}]$ ...

**1**

vote

**2**answers

1k views

### Checking consistency of a system of linear equations and inequalities

I have a lot of systems of equations and inequalities of the following form:
$$ a_{1,1}x+a_{1,2}y+a_{1,3}z+a_{1,4}w = 2 $$
$$ \ldots $$
$$ 0 < x < 2 $$
$$ 0 < y < 2 $$
$$ 0 < z < 2 ...

**4**

votes

**1**answer

169 views

### A requst for clarification of the analysis of the Moser-Tardos algorithmic proof of the Local Lemma

The general form of the Local Lemma can be stated as follows:
Let $\mathcal{A}$ be a finite set of events in a probability space. For $A \in \mathcal{A}$, let $\Gamma(A)$ be a subset of ...

**2**

votes

**6**answers

451 views

### Algorithm to find all (up to isomorphism) perfect matchings of quartic plane graphs

I need to find all (up to isomorphism) perfect matchings of some quartic plane graphs. I haven't found any specific algorithm to give me all the perfect matchings. Does anybody know about such an ...

**2**

votes

**1**answer

195 views

### Nearest trio of neighbours for non-intersecting ellipses

Hi,
I'm working on a problem which is to find the closest trio of neighbours for a set of arbitrarily placed non-intersecting ellipses. As a new user I'm not allowed to include image tags but I've ...

**9**

votes

**2**answers

316 views

### Finding local patterns in a circular list

Consider a list $\boldsymbol{x}=x_0,x_1,\ldots,x_{n-1}$, which we consider to be circular by taking the subscripts modulo $n$. The entries in the list are distinct integers.
A local pattern is a ...

**11**

votes

**2**answers

1k views

### Examples of algorithms that came from category theory?

Generating Compiler Optimizations from Proofs is a wonderful paper. The authors say that they were faced with the problem, got stuck, then tried reasoning about it using category theory. They took ...

**0**

votes

**2**answers

327 views

### Is there a method to find (fit) a function with four (4) independent variables?

I have a system with 4 sensors (say $s_1..s_4$) which I want to combine into a single signal.
I have logged the 4 outputs as well as a "control" sensor ($s_c$) which has the desired ouput signal. ...

**5**

votes

**2**answers

474 views

### Finding the convex combination of vertices which yields an inner point of a polytope

Given a convex polytope $P\in \mathbb{R}^n$, and a point $x\in P$, Caratheodory's theorem gives us that there exists a set of at most $n+1$ vertices of $P$, such that $x$ is a convex combination of ...

**1**

vote

**1**answer

307 views

### Computing the sum over paths through a matrix satisfying constraints

Let $A$ be a $m \times n$ matrix and let Y be the set of paths "from left to right through the matrix"
\begin{equation}
Y=\lbrace 1 \ldots m \rbrace ^N
\end{equation}
Let $f(y;A)$ be the "sum along ...

**-1**

votes

**1**answer

255 views

### What do we mean by “Proving an algorithm”? [closed]

Hello,
Thanks in advance for answering my questions :)
The question is: What do we mean by "Proving an algorithm"?
I'm having a problem in where to start (if I want to use contradiction for ...

**1**

vote

**1**answer

294 views

### An algorithm for constructing the AR-quiver of a path algebra corresponding to a change in the orientation.

Considering the path algebra of the quiver $\mathbb{A}_n$, it is well known its Auslander-Reiten quiver with the canonical orientation of $\mathbb{A}_n$, that is, with all the arrows from, say, left ...

**8**

votes

**3**answers

711 views

### Complexity of matching red and blue points in the plane.

I'm just asking because I'm curious.
I was seeking references on the following problem, that a friend exposed to me last holidays :
Problem
Given $n$ red points and $n$ blue points in the plane in ...

**1**

vote

**2**answers

137 views

### Find most densely located K points among N (N>K) points in two dimension

Suppose I have N points in two dimensional space.
I want to know which K of them are located most densely (so that area occupied by them will be least or sum of squares within cluster is least). ...

**1**

vote

**1**answer

237 views

### Connectivity of a graph with fixed number of vertices and edges

Hi,
first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge.
So this is the ...

**0**

votes

**0**answers

191 views

### Spanning tree that minimizes a dynamic 'metric'

Let us have a graph. When we remove an edge, 2 'cars' are created, one from each vertice of the edge. when these 2 cars meet they stop. The problem is to create a spanning tree so that the sum of the ...

**2**

votes

**1**answer

457 views

### Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...

**4**

votes

**1**answer

315 views

### Graph connectivity related game

I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...

**0**

votes

**2**answers

219 views

### Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function

Given a line function $y = ax + b$, it is easy to calculate the sum-of-squares distance between the line and a window of samples $(1, y_1), (2, y_2), ..., (n, y_n)$ (where $y_1$ is the oldest sample ...

**8**

votes

**3**answers

432 views

### Equitable Allocation of Individuals to Positions

I'm not a mathematician but I working on a problem that feels like it an example of a more general kind of problem and I'm hoping that someone might be able to point me in the right direction.
The ...

**3**

votes

**2**answers

613 views

### Find the maximum set whose subset sum is unique for every of its subset.

We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of numbers such that
for any $T_1,T_2\subseteq S$, the sum of ...

**3**

votes

**2**answers

790 views

### Fast algorithms for addition and multiplication of Zhegalkin polynomials

Hello to all,
I'm interested in fast algorithms for addition and multiplication of Zhegalkin polynomials. For example, let
$f_1(x_1, x_2, x_3) = 1+x_1+x_2x_3$
$f_2(x_1, x_2, x_3) = x_1+x_3$
I'd ...

**4**

votes

**1**answer

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

**1**

vote

**0**answers

519 views

### How to solve simple bilinear equations under extra linear constraints

Hello,
This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:
$\lambda_i^T ...

**4**

votes

**2**answers

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