The algorithms tag has no usage guidance.

**0**

votes

**0**answers

11 views

### are signs of coefficients arbitrary in 01-integer programming?

looking to understand more about full coverage integer programming i wondered if my research should include forms of the problem with the possibility for negative coefficients
i went looking for an ...

**10**

votes

**2**answers

366 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

74 views

+50

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

40 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

55 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

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

**0**

votes

**1**answer

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

**-1**

votes

**0**answers

51 views

### bound on the size of a circuit [closed]

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...

**3**

votes

**1**answer

160 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

253 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

231 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

77 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

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

**12**

votes

**1**answer

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

**21**

votes

**2**answers

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

**21**

votes

**1**answer

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

**5**

votes

**0**answers

68 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

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

**2**

votes

**0**answers

219 views

### Partitioning graph for Graph Isomorphism

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

**27**

votes

**5**answers

6k 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

349 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

834 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

54 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

67 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

114 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

85 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

143 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

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

**10**

votes

**6**answers

960 views

### Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:
Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...

**12**

votes

**1**answer

267 views

### Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question.
Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the ...

**20**

votes

**10**answers

9k views

### Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...

**19**

votes

**4**answers

1k views

### does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...

**4**

votes

**0**answers

40 views

### Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time

A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...

**5**

votes

**4**answers

167 views

### From a (not positive definite) Gram matrix to a (Kac-Moody) Cartan matrix

Suppose I am given a symmetric matrix $G_{ij}$ with $G_{ii} = 2$. Can I always find an invertible integer matrix $S$ such that $(S^T G S)_{ii}=2$ and $(S^T G S)_{ij} \leq 0$ for $i \neq j$? Is there a ...

**1**

vote

**1**answer

174 views

### Finding the “minimum norm” of points in projective space above a prime field

I am working on doing explicit computations finding class groups of quaternions over $\mathbb{Q}$, and the following question (with $n=3$) was a clear choking point:
Given a point $P = [x_0, \dots, ...

**9**

votes

**3**answers

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

**-4**

votes

**1**answer

156 views

### Without the use of a calculator, how to calculate the logarithm of 2 and 3 in base 10 [closed]

Without the use of calculator how to calculate $\log_{10} ~2$, $\log_{10} ~3$?

**4**

votes

**1**answer

579 views

### Finding the vertices of a convex polyhedron from a set of planes

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...

**1**

vote

**1**answer

141 views

### Using Jacobi fields to approximate parallel transport along geodesic:is the following limit true?

I apologize if this is not a research level question (already tried asking http://math.stackexchange.com/questions/1303288/relation-between-parallel-transport-and-jacobi-field-iion stack exchange with ...

**8**

votes

**1**answer

115 views

### Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time

I have the book "Handbook of Computational Group Theory", by Derek Holt, and in it is a section on finding the transversal of a subgroup. Recall a transversal of a subgroup $H$ of $G$ is a single ...

**13**

votes

**4**answers

4k views

### Fast computation of multiplicative inverse modulo q

Given a large number $q$ (say, a prime) and a number $a$ between 2 and $q-1$ what is the fastest algorithm known for computing the inverse of $a$ in the group of residue classes modulo $q$?

**7**

votes

**2**answers

147 views

### Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...

**0**

votes

**0**answers

59 views

### Finding a “special” non singular submatrix

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ ...

**5**

votes

**0**answers

160 views

### Is there a reasoned derivation of the coherence conditions for symmetric rig categories?

I know what the coherence conditions are, I can look them up in
M. Laplaza, Coherence for distributivity, Lecture Notes in Mathematics 281, Springer Verlag, Berlin, 1972, pp. 29-72.
In theory, ...

**3**

votes

**2**answers

168 views

### Paper of Denis Simon on quadratic equations in dimensions 4, 5?

In several places I have come across references to a 2005-6 preprint of Denis Simon entitled
Quadratic equations in dimensions 4, 5, and more
This paper gives fast algorithms to find isotropic ...

**7**

votes

**3**answers

3k views

### Solving a system of linear inequalities — what is the dimension of the solution set?

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...

**5**

votes

**2**answers

202 views

### Ordered lattice point enumeration

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community.
Setup: Let ...

**5**

votes

**1**answer

3k views

### Determine if you can build a polygon from segments [closed]

Is there a way to determine whether it is possible to build a polygon from given n segments?
Maybe triangle inequality generalized?

**4**

votes

**2**answers

262 views

### Breaking a rectangle into smaller rectangles with small diagonals

Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...