Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-...

**3**

votes

**1**answer

40 views

### Separate the trivial partition by a linear hyperspace

Let $e=[1,1,\ldots,1]\in\mathbb{Z}^n$. I am looking for a way to find a vector $a\in\mathbb{Z}^n$ such that:
$\langle a,e\rangle=0$ and
for every nonnegative $v\in\mathbb{Z}^n$ such that $\langle e,v\...

**10**

votes

**1**answer

192 views

### Decide if a matrix is transposable

A matrix $M$ is called transposable if it can be transformed into its transpose $M^t$ via row and column permutations.
Is there an efficient a way/algorithm to decide if a given matrix is ...

**3**

votes

**0**answers

82 views

### Subgroup membership problem for Noetherian groups

I am interested in the status of the subgroup membership problem (MP) for finitely presented Noetherian groups. That is, given a finite presentation $\langle X,R\rangle$ for a Noetherian group,
\begin{...

**1**

vote

**1**answer

78 views

### The complexity of sorting a list having one free cell

Making a standard bureocracy (using Word tables), I arrived to the following
Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say ...

**1**

vote

**0**answers

142 views

### Skew-symmetric multi-derivations of $k[x_1,…,x_n]/I$

Let $I = \langle f_1, \ldots f_r \rangle$ be an ideal in $R=k[x_1,\ldots,x_n]$ where $k$ is a field, and put $A = R/I$.
(If $I$ is prime then $A$ is the coordinate ring of an irreducible affine ...

**2**

votes

**0**answers

39 views

### Karp hardness of two cycles which lengths differ by one

Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is ...

**5**

votes

**1**answer

57 views

### What is the complexity of counting Hamiltonian cycles of a graph?

Since deciding whether a graph contains a Hamiltonian cycle is $NP$-complete, the counting problem which counts the number of such cycles of a graph is $NP$-hard.
Is it also $PP$-hard in the sense ...

**1**

vote

**1**answer

68 views

### In practice, what's the fastest method to find a least square solution rather than using SVD decompostion?

I'm working on a real-time implementation of Lucas-Kanade for optical flow. However, the SVD decomposition to do achieve the least square method to reduce the error seems to take too much time.
A ...

**0**

votes

**0**answers

58 views

### Application of frank wolfe algorithm to non smooth function

I have a function I want to maximize and which is non smooth and non concave/convex
$$ F: [-1,1]^{n \times m} \to \mathbb{R}$$
I know that this function has the same points of non-differentiability ...

**1**

vote

**1**answer

26 views

### Algorithm for cliques in weighted graph

Is there a known algorithm (besides brute force) for the following problem:
We have given an edge-weighted complete graph $G$ and a finite set of natural numbers $A = \lbrace n_1,\ldots,n_k \rbrace$ (...

**7**

votes

**1**answer

157 views

### Counting spanning trees of a planar graph

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...

**0**

votes

**0**answers

13 views

### Making a Graph Eulerian for Applying TSP Heuristics

To rule out isolated vertices, let a graph be called Eulerian, if a tour exists, on which every vertex is encountered at least once and, in which every edge is traversed exactly once.
That definition ...

**2**

votes

**1**answer

128 views

### Decide if a system of arithmetic sequences is an $m$-cover of $\mathbb{N}$

Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences.
For a positive integer $m$...

**-1**

votes

**0**answers

26 views

### Application of non-commutative Khinchine inequality

I am looking for applications of non-commutative Khinchine inequality (see below) in case when Rademacher random variables are tight by the condition $\sum_{i=1}^N\varepsilon_i=M, \, -N \leq M\leq N$....

**1**

vote

**1**answer

141 views

### Shortest bisecting line [closed]

I have troubles finding this:
I don't know how to find this or even write algorithm to do this. Can you help me?
Thanks in advance

**1**

vote

**0**answers

59 views

### Walk in the graph induced by a group action

Suppose that graph $G$ is induced by a group $⟨α_1,...,α_r⟩$ acting on a large finite set $X$ for small $r$. To be precise, we have the vertex set $V(G):=X$,
and $x_1x_2\in E(G)$ whenever for some $\...

**1**

vote

**1**answer

77 views

### How many iterations the best biprime factoring method has to factor a number [closed]

I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...

**9**

votes

**1**answer

274 views

### Are finite presentations of arithmetic groups computable?

In this famous paper by Borel and Harish-Chandra, Arithmetic Subgroups of Algebraic Groups, it is proved that, in characterisitic zero, arithmetic groups are finitely presented. I have an extremely ...

**0**

votes

**0**answers

15 views

### When is the first blocking flow created in Dinic's algorithm a max flow?

When is the first blocking flow created in Dinic's algorithm a max flow? I understand that this is usually an iterated algorithm where one creates level graphs and augments the existing blocking flow ...

**12**

votes

**1**answer

183 views

### Factoring polynomials over the abelian closure of the rationals

What algorithms are known to perform the following task?
Input: a univariate polynomial over the rationals $f \in \mathbb{Q}[t]$.
Output: the factorization of $f$ into irreducible factors over the ...

**9**

votes

**1**answer

306 views

### Fast convolution of sparse functions

Let $F:\mathbb{R}\to \mathbb{Z}$ be a step function with at most $k$ discontinuities, at given rationals $a_1<a_2<\dotsc<a_k$. Let $g:\mathbb{R}\to \mathbb{Z}$ be given as a linear ...

**3**

votes

**0**answers

84 views

### Generating a Penrose tessellation around a given tile

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it.
The following picture illustrates the request:
In this example, the starting tile is a "thin rhombus" (the pink ...

**4**

votes

**2**answers

229 views

### Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...

**3**

votes

**1**answer

92 views

### Matching two sequences between each other

Given the sequence of symbols $A$ (contains ~10,000 symbols) and sequence of blocks $B$ (contains ~3,000 blocks, ~30 symbols inside each block) I need to exclude some blocks from sequence $B$ so that ...

**2**

votes

**0**answers

56 views

### Computational complexity for spectral radius of symmetric matrix

What is the best known algorithmic complexity for computing the spectral radius (largest eigenvalue in magnitude, possibly with respect to some precision and confidence) of a symmetric matrix of size $...

**3**

votes

**0**answers

88 views

### Algorithm detecting all distinct k-th powers in a string for all k ≥ 3

In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.
The ...

**0**

votes

**0**answers

36 views

### A name for algorithms that perform well in an asymptotic sense, when inputs are random

Is there a term for an algorithm that performs "well" (say, within a constant factor of optimality) in an asymptotic sense when a large number of random inputs are provided? For example, say I had an ...

**0**

votes

**1**answer

82 views

### Sampling a uniformly distributed point INSIDE a hypersphere?

There is a simple algorithm to pick a random point ON an $n$-dimensional hypersphere.
Is there one to sample a point from inside it? (Sampling points from a hypercube and rejecting them if they are ...

**2**

votes

**0**answers

56 views

### Recovering a rank-one matrix from its eigendecomposition after randomized rounding

Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...

**38**

votes

**1**answer

721 views

### How to be rigorous about combinatorial algorithms?

1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...

**0**

votes

**0**answers

56 views

### algorithm for maximum sum from root to leaf in a tree (non-binary)

Given some tree with vertices each that can have some variable number of children, is there some algorithm to find the maximum sum from the top of the tree down to one of the leaves? I can see one way ...

**5**

votes

**3**answers

195 views

### Algorithm to decide if the union of a set system covers the power set

Assume that we have a set system $\mathfrak T = \{\mathcal T_1, \mathcal T_2, \dots, \mathcal T_N \}$ where each $\mathcal T_k$ is a collection of subsets of $[n] := \{1,\dots,n\}$ of the form
$$ \...

**2**

votes

**1**answer

181 views

### Name and Algorithms for a Sparsest Circle Packing

The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...

**0**

votes

**0**answers

29 views

### Partitioning ordered objects into sets so as to maximize isolated objects

I'll phrase this as how I thought of it:
Henri is a headmaster who is planning a school trip. He has ordered $n$ coaches to take his $m$ students to the trip destination, and the students have ...

**1**

vote

**0**answers

74 views

### Loopless algorithm for generating permutations (Steinhaus-Johnson-Trotter)

The following is a description of the well-known Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element ground set using adjacent transpositions.
In fact, it is a loopless ...

**1**

vote

**1**answer

89 views

### An variation of an assignment problem in combinatorics: assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. ...

**0**

votes

**0**answers

31 views

### Edgebreaker algorithm over 2-manifolds

Suppose I triangulate a 2-manifold and make a dual pseudograph over it. If I do the Edgebreaker compression algorithm over this graph to generate a spanning tree, can exist an edge with three or more ...

**6**

votes

**0**answers

57 views

### Deciding positivity of real cyclotomic numbers efficiently

Consider a cyclotomic field $\mathbb{Q}[\zeta_n]$ for fixed $n$ and assume that an embedding $\mathbb{Q}[\zeta_n] \hookrightarrow \mathbb{C}$ has been chosen, say by fixing once and for all $\zeta_n=\...

**1**

vote

**0**answers

21 views

### How to express free Lie algebra elements in terms of the right-normed basis?

Article A right normed basis for free Lie algebras and Lyndon–Shirshov words shows that it is possible to build right-normed (right-nested) basis of a free Lie algebra.
I am looking for references (...

**4**

votes

**2**answers

175 views

### Example of concrete statement which requires probabilistic algorithm

In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks ...

**1**

vote

**0**answers

65 views

### Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...

**11**

votes

**0**answers

164 views

### Fast computation of matrix product $AXA^T$ with fixed $A$?

Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...

**3**

votes

**1**answer

106 views

### Strong polynomial algorithm for linear programming

What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?

**9**

votes

**1**answer

174 views

### Find closest integers in Euclidean rings

Assume that $K$ is a number field such that $\mathcal{O}_K$ is a norm-Euclidean ring. I am looking for an efficient algorithm that given an element $x\in K$, find an integer $y\in\mathcal{O}_K$ that ...

**2**

votes

**0**answers

123 views

### An algorithm to compute coherent sheaf cohomology in projective space over a ring [closed]

EDIT: As the article was put on hold, because it was unclear what I am asking, here I put again my two questions:
1) Is the argument I used to derive the algorithm valid?
The second question is a ...

**0**

votes

**0**answers

17 views

### Calculation of Vertex Weights for Combinatorial Optimization of Regular Spanners

Vertex Weights are a means to modify the weight of an edge by adding to it the weights of its adjacent vertices. The motivation for adding vertex weights to edge weights is two-fold: the relative ...

**1**

vote

**1**answer

156 views

### How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?

I am interested in a quantum algorithm that has the following characteristics:
output = 2n bits OR 2 sets of n bits (e.g. 2 x 3 bits)
the number of 1-bits in the first set of n-bits must be equal ...

**6**

votes

**1**answer

299 views

### De-Nesting Absolute Value Function into Linear Combination of Absolute Value Functions

Context: In formulating problems for secondary school mathematics teachers (and students) about absolute value functions, which we define as functions $\mathbb{R} \rightarrow \mathbb{R}$ that send $x \...

**3**

votes

**0**answers

161 views

### Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?

Standard factoring problem $\Pi_1$ is 'Given integers $N$ and $M$ is there a factor $d\in[1,M]$ of $N$?'. This is in $NP$ since such a factor is the witness and in $coNP$ since one can check all the ...

**1**

vote

**0**answers

99 views

### Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...