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,564
questions
3
votes
0
answers
133
views
Recover cyclotomic integer with bounded coefficients from its known associate
Recall that two cyclotomic integers are called associated if their ratio is a unit in the corresponding ring of cyclotomic integers.
We will view cyclotomic integers as polynomials (of degree $<\...
- 30.7k
7
votes
2
answers
800
views
Differential ideal membership problem
We know that in the ordinary algebra ideal case, the ideal membership problem can be solved by the Grobner Base theory, then, is there a counterpart theory in the differential ideal case?
To be ...
- 2,743
8
votes
3
answers
727
views
Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?
Is there any known efficient algorithm (something that works better than brute-force algorithm) to check that given a $(0,1)$-$d \times d$ matrix $A$, is there a permutation matrix $P$ of the same ...
- 27.8k
6
votes
0
answers
63
views
Vertex cover in bipartite graphs with bounds on cost and size
Suppose we have a bipartite graph $G$ with non-negative integer vertex costs. We would like to find a vertex cover of cost at most $C$ and size (number of vertices) at most $S$, where $C$ and $S$ are ...
- 13.7k
2
votes
0
answers
291
views
Perfect matching decomposition algorithm for bipartite regular graphs
It is a well-known result that a bipartite graph can be decomposed into edge-disjoint perfect matchings if and only if it is regular. Now here comes the question. Given a bipartite regular graph, is ...
- 60.4k
0
votes
1
answer
88
views
Enumerating (i.e. generating one by one) matrices of given rank over a finite field
Let be given positive integers $m,n,r$, with $r \leq \min(m, n)$, and a finite field of $q$ elements $\mathbb{F}_q$.
I'm looking for an efficient algorithm to enumerate (i.e., generate one by one) all ...
- 103k
1
vote
0
answers
35
views
Efficient solution to linear matrix equations
A general form for a linear matrix equation can be written as
$$AX + XB + \sum C_iXD_i$$
If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...
- 11
1
vote
0
answers
46
views
How can we hang the weighted trees so that vertices nearer to root (based on distances, not hop count) lie in upper levels?
I have a set of edge weighted trees, each tree rooted at some vertex. Consider these trees are hung from the roots and vertices are arranged in some levels. I wish to design an algorithm (...
- 11.4k
5
votes
1
answer
345
views
Reachability in digraphs
I have a problem that is reducible to (efficiently) determining the reachability of a node in a fully dynamic planar digraph.
I'm aware of "A fully dynamic data structure for reachability in ...
- 1,446
7
votes
2
answers
2k
views
Ideals in the ring of single-variable Laurent polynomials with integer coefficients
I'm writing some software to automatically compute things like Alexander modules, Alexander ideals, Milnor signatures and Farber-Levine pairings for 1 and 2-knot complements. So among other things I'...
- 1,446
23
votes
5
answers
9k
views
Algorithms for finding rational points on an elliptic curve?
I am looking for algorithms on how to find rational points on an elliptic curve $$y^2 = x^3 + a x + b$$ where $a$ and $b$ are integers. Any sort of ideas on how to proceed are welcome. For example, ...
0
votes
0
answers
87
views
Polynomial-time algorithm for exact projection to polyhedral cone
Given $c \in \mathbb{R}^d$ and $A \in \mathbb{R}^{n \times d}$, project $c$ to the polyhedral cone $\{x \in \mathbb{R}^d \mid A x \leq 0\}$. Is there an algorithm that outputs an exact solution to ...
- 1,793
4
votes
1
answer
154
views
Sequence design to optimize a combinatorial objective
Given a set $\cal N$ of $N$ objects, we seek to attribute a code, i.e., a binary sequence, to each of them to achieve the following objective of being capable to select any subset ${\cal S}\subseteq {\...
- 839
44
votes
11
answers
25k
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 ...
- 1
3
votes
4
answers
3k
views
Finding the union of N random circles arbitrarily (or conspiratorially) placed on a two-dimensional surface
Please consider a two-dimensional surface populated with a set of Cartesian coordinates $(x_i, y_i)$ for $N$ circles with individual radii $r_i$, where $r_{\min} < r_i < r_{\max}$.
Here, the ...
- 4,618
1
vote
3
answers
156
views
Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
let $\boldsymbol{X}_1,\,\dots,\,\boldsymbol{X}_n$ be well-ordered sets of positive values and $\mathcal{R}:=\lbrace\left(x_1,\,\dots,\,x_n\right)\rbrace = \boldsymbol{X}_1\times\,\dots\,\times\...
- 18.5k
3
votes
2
answers
559
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 ...
- 2,880
1
vote
1
answer
136
views
3-partition of a special set
$S_5$ is a set consisting of the following 5-length sequences $s$: (1) each digit of $s$ is $a$, $b$, or $c$; (2) $s$ has and only has one digit that is $c$.
$T_5$ is a set consisting of the following ...
- 5,169
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. ...
- 2,743
2
votes
1
answer
70
views
Are there any studies about general lexicographical orderings of Latin Squares and random walks on the space of all such orderings of a given order?
Are there any previous studies about the general lexicographical orderings of Latin squares including random walks the space of all such orderings for a given order of Latin squares?
Are there any ...
- 1,327
20
votes
2
answers
24k
views
Partitioning a polygon into convex parts
I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.
I know almost nothing about this subject, so I've been searching on Google ...
- 4,618
9
votes
2
answers
946
views
Other norms for lattice reduction techniques (LLL, PSLQ)?
LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon ...
- 4,618
1
vote
0
answers
71
views
cut a path from DAG that has minimal conductance
Given a directed acyclic graph $G=(V,E)$, a source node $s$ and a sink node $t$, we want to find a path $P$ from $s$ to $t$ such that if we separate all the nodes in $V$ to two parts $P$ (all the ...
- 143
1
vote
0
answers
62
views
Find a cut of a graph that minimizes the ratio between the edge weights of the cut and the edge weights inside one subgraph
Given an edge-weighted undirected graph $G=(V,E)$ (can assume the weights are non-negative) and a source node $v_s\in V$, a cut is a partition of $G$'s vertices into two complementary sets $S$ and $T$....
- 143
12
votes
2
answers
13k
views
100 Prisoners, 100 Boxes: Proof of Optimality
There's a chestnut about 100 prisoners, labeled 1 through 100, and 100 boxes, each with a number 1 through 100 in it. Each prisoner, completely independently of the others, tries to find the box which ...
- 1,446
9
votes
1
answer
589
views
Square root in number field
I'm trying implement an algorithm that, for an element $b$ of a number field $\mathbb{Q}(\alpha)$, if it is a square in $\mathbb{Q}(\alpha)$ (i.e., $\exists x\in\mathbb{Q}(\alpha):x^2=b$), computes ...
- 4,745
1
vote
0
answers
62
views
Newton-Raphson and bisection for solving for a system of nonlinear equations?
We know that for a single equation root-finding, we can use the Newton's method, or a combination of Newton with bisection to guarantee convergence. Can we use Newton+bisection for a system of ...
- 60.4k
1
vote
0
answers
86
views
Generate the nth permutation [closed]
I'm just trying to write a little algorithm. I've got nine objects, so there's 9! permutations. My question is, is there a way of turning a number from 1 to 9! into a permutation?
for example, f(1)=[1,...
- 60.4k
2
votes
1
answer
163
views
Longest path on directed acyclic graph when the weight is defined on the pair of edges
Given a directed acyclic graph $G=(V,E)$ with a source node $s$ and a sink node $t$, and we have a weight function that is defined on $E\times E$, $f:E\times E\to R^{+}$. We want to find a $s$-$t$ ...
- 221
1
vote
0
answers
95
views
Non-negative least squares: how bad is this heuristic?
The non-negative least squares (NNLS) optimization problem is as follows: for given $A \in \mathbb{R}^{n \times m}$, $y \in \mathbb{R}^n$, find $x \in \mathbb{R}_{\geq 0}^m$ that minimizes $||Ax - y||...
- 5,380
3
votes
1
answer
194
views
Checking presence of a specific term in product polynomial
I have a multivariate polynomial $P$ which is a product of $M$ low degree polynomials $p_i$
$$P(x_1, x_2, \dotsc, x_n) = \prod_{i=1}^M p_i(x_1, x_2, \dotsc, x_n)$$
where the maximum degree of each $...
- 5,169
15
votes
1
answer
351
views
Are hyperbolic $n$-manifolds recursively enumerable?
Fixing a dimension $n \ge 4$, is the class of closed hyperbolic $n$-manifolds recursively enumerable?
Since hyperbolic manifolds are triangulable I can reformulate this in the following more explicit ...
- 66.8k
3
votes
0
answers
130
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
- 10.1k
1
vote
1
answer
135
views
Interpreting optimal matchings as permutations
If $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ is the cost-matrix of an assignment problem, then the usual statement of the problem of finding an optimal assignment is to identify $n$ elements $a_{i,\,\...
- 12.7k
4
votes
0
answers
151
views
Two-player item picking game
Two players $A$ and $B$ play this game: There are $n$ items, where the $i$th item is of value $a_i$ to player $A$ and is of value $b_i$ to player $B$. Two players take turns picking items, and each ...
- 41
5
votes
1
answer
119
views
Algorithms to factorize words into product of powers
I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references.
Let $A$ be a finite set of symbols, are there ...
- 1,141
3
votes
3
answers
117
views
An efficient generalized algorithm to obtain an arbitrary element of a lexicographically ordered tuple of all balanced $l$-bit binary sequences
Assuming that $l>1$ is even, an $l$-bit binary sequence $b$ is balanced if and only if the number of zeroes in $b$ is equal to $l/2$.
Let $T_l$ denote a lexicographically ordered tuple of all ...
- 959
0
votes
1
answer
65
views
Maximum number of teams of fixed size over a score threshold
I am wondering if there is any literature on the following combinatorial optimization problem:
Input: $n, k, T\in \mathbb{N}$ and positive integers $s_1, \ldots, s_n$.
For intuition, we may think ...
- 5,169
2
votes
1
answer
150
views
Verify if array is orthogonal
This is a repost from the computer science stackexchange. The question has been offered a bounty, but received no answers. Therefore, I would like to ask this question here.
Orthogonal arrays often ...
- 10.1k
1
vote
0
answers
71
views
Forming rational numbers using unique Egyptian fractions
Question: For a given rational number $r\in (0,1)$, does there exists a finite, ordered set $S\subset \mathbb{N}$ such that the product of the first $k$ elements of $S$ do not divide the $k+1$th ...
- 121
1
vote
1
answer
117
views
A variant of min-cost flow problem
Given a flow $f$ in graph $G$. For each node $v\in G$, we call the edges ajacent to $v$ containing non-zero quantity of flow as $v$'s active edges. My problem is to find a min-cost flow under the ...
CommunityBot
- 1
15
votes
1
answer
517
views
Make $n$ numbers equal using pairwise averages
Given $n$ rational numbers. Every time you can delete $2$ numbers, and add 2 numbers which are equal to $\frac{a+b}{2}$ (assume the number you delete is $a$ and $b$). How to judge whether it is ...
- 60.4k
3
votes
0
answers
105
views
Tight bounds on the iterates of the Clenshaw algorithm for Chebyshev polynomials
I'm trying to bound the iterates of the Clenshaw algorithm when applied to the Chebyshev series, related to a question I'm running into related to the stability of this algorithm. Recall that, for $p(...
- 101
1
vote
1
answer
341
views
What is the minimum number of multiplications for $2\times 3$ and $3\times 2$ multiplication?
Strassen demonstrated a seven multiplication algorithm for $2\times 2$ matrix multiplication and Winograd showed its optimality.
Let $A$ be $2\times k$ and $B$ be $k\times 2$.
What is the minimum ...
- 6,197
5
votes
3
answers
2k
views
Square root algorithm
I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
- 60.4k
0
votes
2
answers
524
views
Sparse dense matrix versus non-sparse dense matrix in eigenvalue computation
I have a matrix in the form of $2n\times 2n$ block matrix
$$
A = \begin{pmatrix}O& W\\
J& D\end{pmatrix}
$$
where, $O$ is an $n\times n$ zero-matrix; $W$ is a n-by-n diagonal matrix, $W = ...
- 2,743
1
vote
1
answer
117
views
Is there an efficient generalized algorithm to generate a set of binary words satisfying a particular cross-correlation property?
In this question, the term “word” implies a binary word, i.e. a sequence of bits.
Let $W(w)$ denote the number of non-zero bits in a word $w$.
Assuming that $l \geq 2$ is even, an $l$-bit word $w$ is ...
- 6,571
10
votes
0
answers
423
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
- 1,677
1
vote
2
answers
94
views
Minimum edge-weighted directed subgraph in polynomial time
I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
- 5,169
4
votes
2
answers
274
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 5,169