Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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