# Tagged Questions

**3**

votes

**1**answer

143 views

### Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...

**5**

votes

**0**answers

275 views

### Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty).
For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$.
Given some $1\leq s < d$, consider ...

**1**

vote

**1**answer

226 views

### Finding Laurent Series of a function [closed]

I've been assigned to write a computer program which then calculates the Laurent series of a function. Of course I'm familiar with the concept, but I've always calculated the Laurent series in an ad ...

**1**

vote

**1**answer

283 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

229 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

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

**24**

votes

**0**answers

699 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

**2**answers

346 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

90 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

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

**6**

votes

**2**answers

314 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

187 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

198 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

809 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

293 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

292 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

40 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

57 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

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

**12**

votes

**1**answer

311 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

291 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

168 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

76 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

487 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

208 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

119 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

125 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

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

**2**

votes

**1**answer

242 views

### Reducible polynomials

Say one only seeks to identify whether a given polynomial over $\mathbb{Z}[x]$ is reducible, then what are the best ways known to solve this?
$(1)$ If the polynomial is reducible, the algorithm ...

**0**

votes

**1**answer

66 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

138 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

778 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

**1**answer

96 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

140 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

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

**3**

votes

**2**answers

612 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

170 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

466 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

174 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

201 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

281 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

340 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

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

**2**

votes

**0**answers

99 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

157 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

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

**2**

votes

**0**answers

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

**7**

votes

**1**answer

309 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

74 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

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