Questions tagged [algorithms]
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-randomness and algorithmic-topology tags.
1,562
questions
4
votes
2
answers
315
views
Max weighted matching where edge weight depends on the matching
Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
4
votes
0
answers
153
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{...
4
votes
0
answers
188
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
0
answers
193
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 $...
4
votes
0
answers
118
views
Finding short linear combinations in abelian groups
Let $M$ be a finitely generated abelian group. Assume we are given a presentation of $M$, that is
\begin{equation*}
M = \frac{\bigoplus_{i=1}^r \mathbf{Z}g_i}{\sum_{j=1}^s \mathbf{Z} r_j}
\end{...
4
votes
0
answers
274
views
Parity of number of primes
In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of ...
4
votes
0
answers
93
views
Exploiting symmetries to speed up Groebner basis calculation?
Take a collection $F$ of homogeneous polynomials in $\mathbb{C}[x_1,\ldots,x_n]$, along with a finite group $G$ of linear operators over $\mathbb{C}^n$ such that for every $f\in F$ and $g\in G$, we ...
4
votes
0
answers
87
views
Efficient algorithm to construct path augmented graphs with smallest diameter?
I am interested in special graph constructions that have the smallest diameter. We have a path graph $P_n$ ($N$ is even). We add new set of edges $C$ between path nodes such that set $C$ forms a ...
4
votes
0
answers
139
views
In what range can we find diophantine approximations using the LLL-algorithm?
Let $\alpha_1, \ldots, \alpha_n$ be $\mathbb{Q}$-linearly independent real numbers. I want to show that for all $x_1, \ldots, x_n\in\mathbb{Z}$, $|x_i|<N$ we have some lower bound for $\left|\sum ...
4
votes
0
answers
182
views
Optimal instructions for the modular construction of rectlinear Lego structures
Let $X$ be a compact (or periodic) union of integer translates of unit cubes such that the interior of $X$ is connected. (If it makes any difference, suppose that the dimension $n$ of $X$ is 3.) I am ...
4
votes
0
answers
86
views
Efficient CW structures on squarefree semi-algebraic set
General Setup
Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which ...
4
votes
0
answers
123
views
How to enumerate a discrete group of matrices by their Frobenius norm?
Suppose I have a discrete group $G<\mathrm{SL}_2(\mathbb{C})$,
and it is finitely generated by some known generators.
That is, $G=\langle g_1,\dots,g_n\rangle$.
The Frobenius norm of a matrix $m=\...
4
votes
0
answers
146
views
What is the influence of unreliable comparisons on the results of sorting
Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...
4
votes
0
answers
248
views
Comparison of Constrained Optimization Methods
I am trying to solve a constrained optimization problem using filter methods and came across two papers on the topic that I am having some problems with. The original filter method paper is the ...
4
votes
0
answers
2k
views
Weighted Median Filtering
Let's begin with a little review of unweighted median filtering.
Suppose I have a list of $N$ real-valued numbers, $x=x_1,...,x_N$. Let $m_i$ be the median of $K$ consecutive values: $m_i=$ median$(...
4
votes
0
answers
176
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$ ...
4
votes
0
answers
192
views
What is the complexity of intersecting two matrix algebras over a finite field?
The following question arose in a joint project with Arkadius Kalka and Adi Ben-Zvi.
Let $\mathbb{F}$ be a finite field, and $M_n(\mathbb{F})$ be the $n\times n$ matrices over $\mathbb{F}$.
For a ...
4
votes
0
answers
575
views
Minimum number of real multiplications to multiply two quaternions [closed]
Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows:
$$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$
We only need the ...
4
votes
0
answers
174
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 ...
4
votes
0
answers
312
views
Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning? [closed]
I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).
It seems to me that much ...
4
votes
0
answers
220
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 ...
4
votes
0
answers
214
views
What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?
Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...
4
votes
0
answers
130
views
Generating random weak k-bounded reverse plane partitions
Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that $\pi_{ij}...
4
votes
0
answers
351
views
Comparing different Euclidean algorithms on a Euclidean domain
I have posted this question at stackexchange (502413), without responses until now.
In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About ...
4
votes
0
answers
207
views
Rough structure of the double coset space/Graph bijections up to automorphisms
I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...
4
votes
0
answers
171
views
On understanding Discrete-Valued Stochastic Processes( time series, panel data )
It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...
4
votes
0
answers
634
views
Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids
Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.
It ...
4
votes
0
answers
754
views
(Co)limit computations for diagrams of Vector Spaces
Fix a field $K$ and consider a finite directed graph $\Gamma$ where multiple edges between a pair of vertices are allowed so long as the total number of edges is finite. Associate to each vertex $v$ a ...
4
votes
0
answers
391
views
Matching a binary matrix
Given a MxN 0-1 matrix D, with the property that
both M and N are odd numbers
its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).
How do we find M ...
4
votes
0
answers
241
views
Domination in Nice Lattices
Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...
4
votes
0
answers
267
views
Finding generalised Lyndon words
Let $\Sigma = \lbrace a_1, \ldots, a_n, A_1, \ldots A_n \rbrace$ (where $A_i = a_i^{-1}$) and $\prec$ be a total ordering on $\Sigma$.
Let $\Sigma^*$ be the set of all words (generated by the ...
4
votes
0
answers
338
views
Can the Littlewood-Richardson cone be used for combinatorial optimization?
The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times n-$...
4
votes
0
answers
164
views
The mathematics of Schellings segregation model
For those who don't know the model. You can read this pdf. I want to find what is the probability that 2 nodes are each others neighbors when the algorithm converges (i.e. when all nodes are happy).
...
3
votes
4
answers
1k
views
Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?
There is a claim on https://en.wikipedia.org/wiki/Super-recursive_algorithm#Inductive_Turing_machines that 'Simple inductive Turing machines are equivalent to other models of computation such as ...
3
votes
2
answers
2k
views
The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function
I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.
Preliminary: Mertens function and the ...
3
votes
3
answers
2k
views
Is there a simple criterion to determine if two parallelograms intersect?
Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty?
Note that I do not need to actually find the intersection.
3
votes
5
answers
4k
views
Algorithm to find all the cycle bases in a graph
I am given a graph defined by vertexes and edges. I have to obtain all the cycle bases in a network. No coordinates will be given for the nodes.
Here's a sketch that illustrates my point.
Note that ...
3
votes
3
answers
4k
views
L-systems and Sierpinski Triangle
I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below).
I'm interested to know how could one arrange the rules of ...
3
votes
4
answers
3k
views
Algorithm to find the “optimal” path in a given graph
Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
3
votes
2
answers
554
views
How to tell if two or more knots are linked
Given a number of knots, I would like to know if they are linked. I know that the linking number can tell if two knots are linked.
There is any method that completely solves this problem?
3
votes
3
answers
210
views
Rank(A) and other algorithms as a polynomial
If $A = (\alpha_{ij}) \in \mathbb{C}^{nxm}$ we have simple algorithms by which to determine $\mathrm{rank}(A)$. However, is there a polynomial $f \in \mathbb{C}[\alpha_{ij}]$ where $f \colon \mathbb{C}...
3
votes
1
answer
216
views
Computabillity of packing of spheres with different radii
This is a conceptually easier version of a box packing problem I stated earlier.
Let $n$ be a positive integer and let $r_1, \ldots, r_n$ be positive integers. We take $r_i$ to be the radius of a ...
3
votes
2
answers
1k
views
Enclosing a set of ellipses within one ellipse
Is there an algorithm that takes in a set of ellipses and gives back an ellipse that encloses the original set of ellipses?
3
votes
1
answer
354
views
$\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)$ Double Summing a (Not Completely) Multiplicative Function
Let $f(n)$ be a multiplicative function that is not completely multiplicative, i.e $f(m)\cdot f(n)= f(m\cdot n)$ only if $gcd(m,n)=1$. Let $S(x)$ be the double sum over $f$, that is:
$$S(x)=\sum_{i=1}...
3
votes
2
answers
557
views
Complexity of establishing finite groups (non)-isomorphism ?
Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N ...
3
votes
4
answers
2k
views
Enumerative algorithm through inclusion-exclusion
Hello everybody !
I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. ...
3
votes
2
answers
313
views
Is this BBP-type formula for $\ln 31$, $\ln 127$, and other Mersenne numbers also true?
In this post, a binary BBP-type formula for Fermat numbers $F_m$ was discussed as (with a small tweak),
$$\ln(2^b+1) = \frac{b}{2^{a-1}}\sum_{n=0}^\infty\frac{1}{(2^a)^n}\left(\sum_{j=1}^{a-1}\frac{...
3
votes
2
answers
984
views
Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances
Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances.
The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
3
votes
1
answer
443
views
Does a product of matrices have eigenvalue 1
Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$.
For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an ...
3
votes
1
answer
433
views
Find the least prime $p$ such that $mn$ divides $p-1$
My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.
Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ ...