The algorithms tag has no usage guidance.

**4**

votes

**1**answer

233 views

### Listing all solutions to $n = x^2 + y^2 + z^2 $ with integers

I would like to list all ways of writing $n$ as the sum of 3 squares. This is slightly different from finding just one:
Is there an algorithm for writing a number as a sum of three squares?
...

**2**

votes

**1**answer

71 views

### Asymptotic upper bound for recursive function $f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$

I'm looking for an asymptotic upper bound for the function f(x), which is recursively defined as follows: $$f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$$
with $f(1)=1$. I am pretty ...

**-1**

votes

**0**answers

19 views

### Relaxation methods for nonlinear PDE boundary value problem

I have the following type of PDE $$\frac{\partial u}{\partial t} = A - B u + \nabla^2 u^2 $$ For the relaxed system I need to solve therefore $$0 = A - B u + \nabla^2 u^2 $$
Could someone address me ...

**6**

votes

**3**answers

190 views

### Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**3**

votes

**1**answer

70 views

### Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...

**-1**

votes

**0**answers

38 views

### Quicksort - Pivot selection Random Element vs. Random Index [closed]

I have an array of size 1 to n which contains number from 1 to 10 ( floating point numbers included). Which strategy is better to pick up a pivot for Quicksort -
1. Picking a random element between 1 ...

**0**

votes

**1**answer

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

**2**

votes

**0**answers

72 views

### Computing the density of a set of multiples

Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...

**8**

votes

**3**answers

435 views

### Is the Number of Carries in Integer-Addition Associative?

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions ...

**2**

votes

**0**answers

79 views

### Worst case performance of a simple averaging algorithm

Let $u_1,\ldots,u_n$ be a sequence of rationals with finite binary expansion.
Consider the following simple averaging algorithm:
while the sequence is not monotone increasing, pick $i$ with ...

**5**

votes

**1**answer

105 views

### Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Is there a polynomial analog of this problem ...

**-1**

votes

**0**answers

42 views

### Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include:
All vectors in $S$
All vectors in $T$
All vectors that can be ...

**6**

votes

**2**answers

422 views

### What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in ...

**12**

votes

**1**answer

919 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**0**

votes

**0**answers

214 views

### Reduction to some physical interpretation of this formula

Problem Given N 3-dimensional points which are {$p_1,p_2,..,p_n$} where $p_i = (x_i,y_i,z_i) $ . I have to find the value of the formula
$$ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n \frac{ \mid ...

**10**

votes

**4**answers

449 views

### Computing minimal polynomials using LLL

I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation ...

**21**

votes

**2**answers

329 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**16**

votes

**5**answers

2k views

### How Does One Find the “Loneliest Person on the Planet”?

I'm looking for the algorithm that efficiently locates the "Loneliest Person on the Planet", where "loneliest" is defined as:
Maximum minimum distance to another person -- that is, the person for ...

**2**

votes

**0**answers

32 views

### Algorithm to get lower peak of bimodal histogram [closed]

I have a set of data, when tabulated in histogram, it looks like bimodal histogram.
With naked eyes, we can see the value for lower peak is about -1.35, however, what algorithm I can use to ...

**2**

votes

**3**answers

77 views

### Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...

**2**

votes

**1**answer

99 views

### Mestre-type algorithm for higher-genus curves?

Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...

**15**

votes

**2**answers

830 views

### Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...

**4**

votes

**3**answers

258 views

### Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$.
Given $g$ and either
$$ A = x g^ x$$
or
$$ A = x g^{x^2-1}$$
find $x$.
What is the complexity of solving this?
Is there a reduction to the discrete ...

**7**

votes

**1**answer

274 views

### Algorithmic decidability of equality in the ring of periods

Suppose two elements of the ring of periods are given by their systems of polynomial inequalities with rational coefficients. Is there a known algorithm deciding their equality? Is it known if their ...

**0**

votes

**2**answers

801 views

### Largest subarray with average $\geq$ k

I try to solve this problem. The algorithm I developped has a complexity of $O(n^2)$. When dealing with large data the program is brought to its knees. Do you have any idea that might be faster than a ...

**9**

votes

**2**answers

416 views

### Decidability in Groups

This is not my area of research, but I am curious. Let $G=\left< X|R \right>$ be a finitely presented group, where $X$ and $R$ are finite. There are many questions which are undecidable for all ...

**2**

votes

**0**answers

242 views

### Partitioning graph for Graph Isomorphism [closed]

Motivation: I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases .
Construction:
$G$ is an $r$ regular graph, $k$ connected (not a ...

**10**

votes

**3**answers

447 views

### Continued Fractions from Digit Streams

let $x=\sum_{i=1}^{\infty}\delta_i2^{-i},\ \delta_i\in\{0,1\}$.
Is there an algorithm that converts the sequence $(\delta_0,\ \delta_1,\ ...)$ of the binary digits of $x$ to the sequence ...

**5**

votes

**0**answers

104 views

### Biggest (or large) rectangle in a polytope

I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...

**4**

votes

**0**answers

52 views

### Algorithm to express a point from a H-polyhedron as convex combination of extreme points

Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is,
$$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$
Let $\boldsymbol{x} \in P$. We ...

**0**

votes

**0**answers

89 views

### Probability two random intervals overlap

I'm working on an algorithm for orthogonal line intersection detection and am trying to analyze some things about it. For simplicity, we can consider the problem as follows:
Given N randomly ...

**0**

votes

**1**answer

166 views

### A three variable linear diophantine promise problem

Given $a,b,c,s\in\Bbb N$ such that $(a,b,c)=1$ with promise that we have at most one triple $x,y,z\in\Bbb N$ such that $ax+by+cz=s$, what is a good algorithm that runs in $O(\log(abcs))$ time to find ...

**3**

votes

**1**answer

164 views

### Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...

**2**

votes

**1**answer

260 views

### Is there an algorithm to test whether a vector is an eigenvector of a power of a matrix?

Given a square matrix $A\in k^{n\times n}$ and a vector $x\in k^n$ over some field $k$, is there an algorithm to test whether there are $s\in\mathbb{N}$ and $\lambda\in k$ such that $A^sx=\lambda x$? ...

**3**

votes

**1**answer

232 views

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

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

**0**

votes

**0**answers

87 views

### Coxeter Subgroups of Coxeter Groups

Is there an algorithm to determine all the Coxeter subgroups of a given Coxeter group? If we only want the Coxeter subgroups of finite index does that make the question easier? If we only want a ...

**7**

votes

**1**answer

107 views

### Determine if an $n$-dimensional mesh of simplices is a non-manifold

In an $n$-dimensional space I have a set of simplices where each simplex consists of facets. Some of the simplices are 'connected' by sharing facets. Each facet is made up on edges, each consisting ...

**21**

votes

**2**answers

764 views

### Groups where word problem is solvable, but not quickly?

Are there finitely generated groups whose word problem is solvable, but not quickly? It would be great to have specific examples, but existence results would also be helpful.
All of the groups that ...

**5**

votes

**0**answers

76 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**0**

votes

**0**answers

49 views

### Best measure for curve similarity

I would like to measure similarity between two curves represented by two arrays of points.
The similarity measure should not depend on the size of these shapes. Two similar shapes but have different ...

**27**

votes

**5**answers

7k views

### Computing the Galois group of a polynomial

Does there exist an algorithm which computes the Galois group of a polynomial
$p(x) \in \mathbb{Z}[x]$? Feel free to interpret this question in any reasonable manner. For example, if the degree of ...

**5**

votes

**4**answers

368 views

### Deceptive linear algebra problem

Does anyone recognize this problem? There are $2p$ equations and $2p$ unknowns, and it feels like a classic, but I've never encountered it before:
Given $d_1, d_2, \ldots d_p$, find $a_1, a_2, \ldots ...

**6**

votes

**4**answers

847 views

### Simplex method for SDP?

I know the interior point method works both for Linear Programming (LP) and semidefinite programming (SDP). My question is, can the other popular method for solving LP, namely the simplex method, be ...

**2**

votes

**1**answer

56 views

### Maximal opening angle of a polygon from a point [closed]

I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point.
One ...

**7**

votes

**6**answers

1k views

### Which model of computation is “the best”?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...

**2**

votes

**1**answer

69 views

### Equality of Euclidean numbers / constructible numbers

Euclidean numbers are those real number that can be constructed from the natural numbers by a finite chain of +,-,*,/ and $\sqrt{}$. They are also called Constructible Numbers.
I am now interested in ...

**0**

votes

**2**answers

117 views

### Generate all non-isomorphic partitions $\pi = \{ \{1, …, n-1\}, \{n\} \}$ for all graphs of order $n$

Let $G$ be any connected, undirected, and unweighted graph of order $n$.
Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster ...

**5**

votes

**1**answer

92 views

### Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...

**4**

votes

**0**answers

146 views

### What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...

**2**

votes

**0**answers

197 views

### Does knowing $g, g^r, g^{r^2}, g^{r^3}, \dotsc$ sometimes offer a significant advantage in finding $r$?

Is there a cyclic group $\mathcal G$ with generator $g$ for which the discrete log problem is assumed to be hard, but knowing $g, g^r, g^{r^2}, g^{r^3}, \dotsc$ for random $r$ makes finding $r$ easy?
...