The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
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
2answers
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
2answers
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
0answers
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
3answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
6answers
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
1answer
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
2answers
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
2answers
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
2answers
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
2answers
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
1answer
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
1answer
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
1answer
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
3answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
3answers
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
2answers
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
2answers
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
1answer
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
0answers
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
2answers
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 ...