The algorithms tag has no wiki summary.

**0**

votes

**0**answers

63 views

### Generating alternating cycles on a perfect matching

Given a perfect matching $M$ in a regular bipartite graph $G$, is there an efficient algorithm to randomly generate self-avoiding alternating cycles with uniform distribution? Ideally, such an ...

**1**

vote

**1**answer

121 views

### Computation Complexity for Golden Section method

I need to provide computational complexity for the algorithms in my work. One of the algorithms I have used is Golden Section method for line search. I took a look at "Nonlinear Programming" book by ...

**4**

votes

**2**answers

221 views

### An algorithm to compare two representations of a simple Lie algebra?

I have two representations of a simple (complex or real) finite-dimensional Lie algebra $S$, both given in terms of their structure constants on a given basis.
the first one is the adjoint ...

**2**

votes

**0**answers

60 views

### Computing maximal ideals of a Lie algebra

Would you know an algorithm (or an automatic method) that computes all maximal ideals $J$ of a given Lie algebra?
Or an algorithm that computes all maximal ideals $J$ containing a given minimal ideal ...

**22**

votes

**0**answers

668 views

### On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...

**2**

votes

**1**answer

217 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**1**

vote

**1**answer

85 views

### QR decomposition of matrix [closed]

I have matrix $M = \begin{pmatrix} A & B \\ B^T & 0\end{pmatrix}$, where $A$ is $N\times N$, $B$ is $N\times 2$ and I have $Q$, $R$ such that $A = QR$. What is the fastest way to find $Q'$ and ...

**7**

votes

**0**answers

144 views

### Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?

Landau's function
$g(n)$ is the largest order of an element of the symmetric group $S_n$.
Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$.
In general $g(n)$ is ...

**7**

votes

**2**answers

291 views

### Minimum number of unit fractions to sum up a given positive rational

For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$, see this article by Paul Erdös and Sherman Stein ...

**0**

votes

**0**answers

93 views

### Parallelism degree of a DAG

Let me first give a motivation. Suppose a connected DAG G with one source X and one sink Y. The goal is to find some "bottleneck" node between X and Y, i.e. node through which every path from X to Y ...

**3**

votes

**1**answer

153 views

### Sorting interleaved sorted lists

By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and ...

**8**

votes

**4**answers

745 views

### What does it mean when we say we have computed a number to a certain accuracy using a probabilistic algorithm?

My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples.
Let me start the discussion with ...

**1**

vote

**2**answers

237 views

### Regular paths along surface of sphere

I'm trying to create a program where a small ball is supposed to move along the surface of a sphere, which is given by its radius $r$ and the center $c$.
The movement should be repetitive, so that ...

**1**

vote

**1**answer

190 views

### Can we find structure constants of Lie Algebra for Lie Symmetry of ODE without solving determining equations?

Let's consider (for example) one scalar ODE.
We are searching for Lie Symmetries of it.
There is well-known result, that we can find size of Symmetry Group without solving determining equations.
...

**0**

votes

**0**answers

31 views

### how to efficiently compute the mean function for non-homogeneous poisson process?

Suppose that I know all intensity functions lambda(t) during given period [0,t], how can I compute the mean function m(t) for non-homogeneous Poisson process?
Basically, m(t) in the integral of ...

**2**

votes

**0**answers

48 views

### finding dominating cycles in $2K_2$-free graphs

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in ...

**3**

votes

**1**answer

147 views

### How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?

First some
Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...

**11**

votes

**1**answer

201 views

### Fastest algorithm to compute the width of a poset

An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out ...

**5**

votes

**2**answers

217 views

### Compute adjugate matrix over commutative ring

Let $A$ be a $n\times n$ matrix over a commutative ring. I'm looking for a good method to compute its adjugate matrix.
My current approach is to use the Cayley-Hamilton theorem:
$$\text{adj}(A) = ...

**1**

vote

**0**answers

125 views

### NP hard problems on geometric graphs

I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...

**1**

vote

**0**answers

64 views

### Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem.
The algorithm states:
For graph G
create an edge from target to ...

**6**

votes

**1**answer

459 views

### How to test if the power of some algebraic number is the rational combination of two specific algebraic numbers?

Suppose we are given three algebraic numbers $\alpha,\beta,\gamma$ by presenting their minimal polynomial (degree less than $m$), the goal is to compute all positive integers $n$ such that $\alpha^n$ ...

**4**

votes

**1**answer

179 views

### Resolvent of a triangular matrix

Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$?
Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the ...

**-2**

votes

**1**answer

101 views

### how to reduce 3-colorable graph to this? [closed]

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...

**0**

votes

**0**answers

120 views

### E- and A-algorithms for finite arithmetic prime progressions and other sets

(EDIT from scratch).
Let $\ \mathbf a := (a_1\ \ldots\ a_n)\ $ be an increasing non-constant arithmetic progression of odd positive numbers. The goal here is to resolve efficiently one of the two ...

**4**

votes

**1**answer

161 views

### Decomposing representations of finite groups of Lie type via computer

This is related to my previous question here.
Let me remind you what that question asked:
Let $\text{St}_n(\mathbb{F}_q)$ be the Steinberg module (over $\mathbb{C}$) for ...

**0**

votes

**1**answer

61 views

### Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?

**1**

vote

**0**answers

122 views

### Explicitly showing that a free group is LERF [closed]

Let $F$ be a free group on a finite set $X$, and let $M$ be a finitely generated subgroup.
Marshall Hall's theorem states that $M$ is closed in the profinite topology on $F$. That is, $M$ is the ...

**8**

votes

**1**answer

376 views

### Algorithm to produce random number with a gamma distribution

I'd like to produce pseudo-random numbers with different distributions for a Monte Carlo simulation.
I've got the poisson distribution working nicely with an algorithm from Knuth. I'm having trouble ...

**0**

votes

**0**answers

148 views

### Trilateration issues, when circles don't intersect

I'm working on Indoor localization where I've deployed multiple iBeacons in my environment. I'm taking distances from all the beacons through their RSSI values. They are not 100% accurate though. Now ...

**0**

votes

**1**answer

84 views

### Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex.
In other ...

**2**

votes

**1**answer

132 views

### DL-problem on abelian variety

Let $A$ be an abelian variety over $\mathbb{F_q}$ with dimension $n$. Let $q$ be a constant.
Is there polynomial algorithm of finding discrete logarithm in $A$?
UPD: really I don't undestend: can we ...

**3**

votes

**2**answers

359 views

### Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...

**2**

votes

**1**answer

357 views

### Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...

**5**

votes

**3**answers

147 views

### Minimize distance between centroids of subsets of points

In a n-dimensional space, I want to divide a set of m points into v (non-empty) subsets.
I want to minimize the sum of the pairwise Euclidean distances between the centroids of the resulting subsets.
...

**3**

votes

**1**answer

311 views

### Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...

**3**

votes

**1**answer

138 views

### Existence of subgraphs when given its degree sequence

For a given simple graph $G$ with $n$ vertices $v_1,v_2,\dots v_n$, the corresponding degree sequence is $d_1,d_2,\cdots,d_n$. My qusetion is:
How to determine whether there exist subgraphs in $G$ ...

**4**

votes

**0**answers

194 views

### Navigation in a graph

The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...

**3**

votes

**0**answers

216 views

### What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...

**14**

votes

**2**answers

320 views

### Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...

**1**

vote

**0**answers

57 views

### Is there an efficient algorithm for sampling from the negative hypergeometric distribution? [closed]

I'm writing a small statistics library currently. One of the algorithms I'm implementing has two variants: one that samples the hypergeometric distribution and one that samples the negative ...

**3**

votes

**0**answers

83 views

### Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...

**1**

vote

**2**answers

146 views

### Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...

**2**

votes

**1**answer

105 views

### enumeration of connected blocks in finite size square

Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected?
By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we ...

**1**

vote

**0**answers

88 views

### Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here.
I want to know the optimal complexity of an algorithm (I mean the ...

**5**

votes

**1**answer

217 views

### Modular polynomials for elliptic curves point counting

The Schoof-Elkies-Atkin (SEA) algorithm (for counting points on elliptic curves over a finite field) performs computations over polynomials modulo some modular polynomials. Originally the "classical" ...

**0**

votes

**1**answer

72 views

### Paper on unit disk graphs

I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?

**3**

votes

**1**answer

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

**6**

votes

**1**answer

176 views

### Constructing sums of squares identities

Recall that a sum of squares formula for $[r,s,n]$ over a field $F$ is an identity of the form
$$ ( x_{1}^{2} + \cdots + x_{r}^{2})( y_{1}^{2} + \cdots + y_{s}^{2})
= ( z_{1}^{2} + \cdots + ...

**10**

votes

**3**answers

520 views

### Square filling self avoiding walk

I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and ...