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.
463
questions with no upvoted or accepted answers
2
votes
0
answers
130
views
Time complexity of randomized algorithm: right-multiplying by random elements $z_i$ from a group $H$ to achieve $H$-invariance
Note: This question was inspired by a related question about the Quantum Merlin Arthur (QMA) complexity class on Quantum Computing Stack Exchange. I was deliberating whether to ask this on CS Theory ...
- 259
2
votes
0
answers
84
views
Given positions find the symmetry group
Given a finite set of vectors in $\mathbb{R}^n$ ($n=2,3$),
is there any algorithm to find its symmetry group?
For example, if the input is {(1,0),(0,1),(-1,0),(0,-1)}, then the output is the dihedral ...
2
votes
0
answers
100
views
Check rapidly if a map of finite groups is a homomorphism
I have two non-abelian finite groups $G$ and $H$ of equal size $n$ and a map $f$ from the underlying set of $G$ to the underlying set of $H$. I store the groups as their multiplication tables (i.e. ...
- 21
2
votes
1
answer
312
views
Worst case performance of heuristic for the non-Eulerian windy postman problem
The windy postman problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...
- 12.7k
2
votes
0
answers
135
views
Calculating Minimum Spanning Trees in Very Big Graphs
I need to determine Minimum Spanning Trees (MST) of very big complete graphs, whose edgeweights can be calculated from data that is associated with the vertices.
In the planar euclidean case, for ...
- 12.7k
2
votes
0
answers
35
views
Difference Between Total Least Squares Plane and Plane Orthogonal to Principal Axis of Inertia Tensor
Given a finite set $P$ of points in $\mathbb{E}^3$ , one can calculate an approximating plane either as the solution of a Total Least Squares problem or by interpreting the problem physically, ...
- 12.7k
2
votes
0
answers
27
views
Complexity of weighted fractional edge coloring
Given an edge-weighted multigraph $G=(V,E)$ with a positive, rational weight function $(w(e): e \in E)$, the weighted fractional edge coloring problem (WFECP) is to compute ($\min 1^T x$ subject to $...
- 151
2
votes
0
answers
223
views
Heuristic for lower bounding the time for integer factorization?
I am posting this question here in hope that someone finds this heuristic useful, and maybe someone with more experience will make use of this:
As @GerryMyerson suggested here is a statement of what ...
user6671
2
votes
0
answers
442
views
Succinct circuits and NEXPTIME-complete problems
I am fascinated by a recent fact I was reading: Succinct Circuits are simple machines used to descibe graphs in exponentially less space, which leads to the downside that solving a problem on that ...
- 41
2
votes
0
answers
74
views
Fastest Algorithm to calculate Graph pebbling number?
I am interested in Graph Pebbling, and in particular what are the fastest known algorithm is to find the pebbling number of a graph. Also, i am interested whether there are lower limits on the runtime ...
- 41
2
votes
0
answers
125
views
Can one optimize the probability that an identity is satisfied until the probability is $1$?
I wonder how well one can obtain algebraic structures that satisfy interesting algebraic identities by simply slowly modifying those algebraic structures until they satisfy the required identities. I ...
- 27.8k
2
votes
0
answers
219
views
Known Methods for "Mutexing" Antiparallel Arcs in Graphs
I recently faced the problem of calculating shortest paths in undirected graphs in the presence of negative edge weights; I could not find any applicable algorithms via online search.
Transforming the ...
- 12.7k
2
votes
0
answers
76
views
First appearance of "structure tree"?
Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges ...
- 19.4k
2
votes
0
answers
82
views
Stochastic Approximation Algorithms Converging to Local Equilibriums
Consider the stochastic iterative updates
\begin{align}
\theta_{t+1} \leftarrow \theta_t + \alpha_t \cdot \left [ h(\theta_t) + M_t \right ],
\end{align}
where $\theta_t \in \mathrm{R}^d$, $h \colon ...
- 1,127
2
votes
0
answers
113
views
Complexity of tensor decomposition vector over $\Bbb F_q$ or $\Bbb Z$
Suppose we have a matrix $$T\in\Bbb K^{n^k\times m}$$ and a target vector $v\in\Bbb F_q^m$ where $m<n^k$ and $1<k$ holds.
We need to find $k$ vectors $u_1,\dots,u_k\in\Bbb K^n$ such that $$v=...
- 13.7k
2
votes
0
answers
176
views
Can the Moler and Morrison Algorithm be Improved?
In a nutshell, the Moler and Morrison algorithm is a fast method for calculating euclidean distances in a numerically stable way by using reflections instead of the pythagorean theorem.
In order ...
- 12.7k
2
votes
0
answers
789
views
Inverse set cover problem
Given a universe $U$, and a set of subsets $S=\{S_i:S_i\subseteq U\}$, find $k$ such subsets so that their union size is minimal.
Is there a name for this problem? Is it NP? Are there efficient ...
- 21
2
votes
0
answers
121
views
Randomized algorithm to verify the uniqueness of non-negative solution to a linear system
Assume we have the under-determined linear system
$$
Ax = y
$$
$$A \in \mathbb R^{m \times n}_{\geq 0},\, y \in \mathbb R^m_{\geq 0},\, m < n,$$ for which we know a non-negative solution $x^* \in \...
- 325
2
votes
0
answers
109
views
Does there exist a linear-time algorithm to find a basis of the null space of the adjacency matrix of a tree?
I am working on a decomposition of trees based on the null space of the adjacency matrix of the tree. Most algorithm on trees are really fast. The decomposition could give some algorithms to find ...
2
votes
0
answers
146
views
Is pos(n) an algorithmic counter?
Let $\ \mathbf N = \{1\ 2\ \ldots\}\ $ be the set of natural numbers. Let $\ f : \mathbf N\rightarrow\mathbf N\ $ be an arbitrary function, and $\ \forall_{n\in\mathbf N}\, F(n)\ :=\ \max_{k = 1\ldots ...
- 7,472
2
votes
0
answers
452
views
Finding good high-dimensional sphere coverings in Euclidean space
Suppose we want to cover the unit sphere $\mathcal{S}^{d-1} := \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ with spherical caps $\mathcal{C}_{\mathbf{y}} := \{\mathbf{x} \in \mathcal{S}^{d-1}...
- 723
2
votes
0
answers
61
views
Finding orthogonal basis with constraint
Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...
- 909
2
votes
0
answers
53
views
smallest ball enclosing one point of each color
I have a set of colored points (say 10 colors with 50 points of each color) in a 100-dimensional space. I want to choose one point of each color so that the 10 points are as close to each other as ...
- 21
2
votes
0
answers
96
views
Calculating a Combinatorial Generalization of Planar Convex Hulls
In this question I have suggested a generalization of the notion of a set of points in the Euclidean plane being in convex configuration to the set of vertices of symmetric weighted graphs via $k$-...
- 12.7k
2
votes
0
answers
104
views
Is there a name for this variant of the MST and the TSP?
Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...
- 3,929
2
votes
0
answers
120
views
Blossoms and Colorings
There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...
- 12.7k
2
votes
0
answers
303
views
Avoiding Chinese Remainder Theorem
Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
user76479
2
votes
0
answers
106
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 $u_{i+1}&...
- 3,771
2
votes
0
answers
235
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?
...
- 4,843
2
votes
0
answers
80
views
A basic minimization problem over finite fields
Let $p$ be a prime, and suppose we are given $n$ values mod $p$: $a_1,...,a_n\in Z_p$. Is there a fast algorithm for finding $\alpha\in Z_p$ which minimizes the value $\max_i (\alpha\cdot a_i$ mod $p$...
- 21
2
votes
0
answers
71
views
Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M
this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)
Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...
- 21
2
votes
0
answers
206
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 ...
- 73
2
votes
0
answers
324
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 ...
- 903
2
votes
0
answers
118
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 ...
2
votes
0
answers
264
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 ...
- 1,785
2
votes
0
answers
458
views
Computing the chromatic polynomial of graph modulo $x-3$
The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...
- 24.2k
2
votes
0
answers
595
views
Is finding a single vector in the null space as difficult as discovering the whole null space?
Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is:
Is the ...
- 163
2
votes
0
answers
138
views
Lanczos algorithm with thick restart on a dynamic matrix
currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...
- 21
2
votes
0
answers
75
views
Smallest distribution of points with genuinely different clusterings
An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...
- 9,628
2
votes
0
answers
44
views
largest size for a randomness extractor
I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
- 1,109
2
votes
0
answers
260
views
Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix
I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers.
To be precise, I want ...
- 21
2
votes
0
answers
39
views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
- 21
2
votes
0
answers
84
views
Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case
I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...
- 21
2
votes
0
answers
658
views
Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin
Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them?
Background:
Thanks to Will Jagy ...
- 21
2
votes
0
answers
190
views
Choosing a base where a given digit of a given number appears the most times
Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)
- 29
2
votes
0
answers
178
views
Randomized alternative to Buchberger's algorithm
Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra.
Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...
- 529
2
votes
0
answers
310
views
Algorithm for keeping a concrete version of Euclid's argument simple
(A version of this same question was posted to stackexchange.)
Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...
- 11.9k
2
votes
0
answers
378
views
Prime generating algorithm
If I want an algorithm that outputs any $n$ distinct prime numbers, is there anything faster than Atkins' Sieve $O(n/log(log(n))$ ?
- 272
2
votes
0
answers
635
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of rectangular ...
2
votes
0
answers
186
views
Recovering a linear map from a non-linear approximation
The problem described here is algorithmic. We are given "black box access" to a map $f:R^d\to R^d$. By this we mean that one may query the value of $f(v)$ for an arbitrary $v\in R^d$.
We assume that ...
