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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 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 ...
user avatar
1 vote
0 answers
57 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 ...
user avatar
  • 121
2 votes
1 answer
117 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 ...
user avatar
  • 470
0 votes
0 answers
34 views

Find number of overlapping edges in a one-dimensional graph

I have a set of edges $(v_1, v_2), (v_2, v_3),(v_2, v_4)$ where each edge has a weight. Say the weights are 1, 2 and 3 respectively. Then we can visualise it as 3 threads, where the the thread from ...
user avatar
2 votes
1 answer
190 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 ...
user avatar
  • 12.8k
15 votes
1 answer
364 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 ...
user avatar
  • 151
12 votes
4 answers
3k views

Why is fast matrix multiplication impractical?

I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication. I read some content saying fast matrix multiplications are impractical because of large ...
user avatar
6 votes
0 answers
167 views

Algorithmically handling the Spin groups in larg(ish) dimensions

Question: Is there a reasonably efficient algorithmic representation of $\mathit{Spin}_n$? By this I mean, a way to store its elements and operate on them (multiply, inverse, maybe compute ...
user avatar
  • 21.7k
1 vote
1 answer
97 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 ...
user avatar
3 votes
0 answers
57 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(...
user avatar
  • 101
1 vote
2 answers
61 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 ...
user avatar
4 votes
2 answers
118 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 ...
user avatar
8 votes
0 answers
269 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$...
user avatar
3 votes
1 answer
71 views

Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation

Given a matrix group $G$ by its generators i.e. $G =\langle A_1,A_2,...,A_k \rangle \leq GL_n(q)$, where each $A_i$'s are matrix in $GL_n(q)$ Q. Does there exist a polynomial time (polynomial in ...
user avatar
  • 143
0 votes
0 answers
17 views

generalized transitive reduction of a directed graph

The transitive reduction of a graph $G$ is a graph with the same vertices that preserves reachability: a path from $a$ to $b$ exists in the reduced graph if and only if one exists in the original ...
user avatar
  • 131
7 votes
1 answer
202 views

Finding maximal prefix of a simple curve

Let $S$ be a piecewise-linear simple curve. For a point $p_1$ on $S$ I want to determine a maximal interval $I$ on $S$ starting in $p_1$ such that $I$ is contained in a unit disk. Is this possible, or ...
user avatar
  • 73
10 votes
1 answer
277 views

Can you get any natural number from 4 by performing given operations?

You can perform the following operations on numbers: divide the number by 2, add 0 or 4 at the end of the number. Can you get any natural number from 4 by performing only these operations? So far I ...
user avatar
  • 119
0 votes
0 answers
47 views

Entropy maximisation of argmax over random vector

Let's say I have a vector of continuous random variables $X=[x_1, x_2, ..., x_n]$. Each one of them has its own pdf $p(x_i)$. Let us define a new random variable $i$ given by $i=\arg\max X$. The ...
user avatar
  • 123
1 vote
0 answers
41 views

Standard test for the recognition of toroidal graphs

Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer–Myrvold planarity algorithm, which has a MATLAB and C++ implementation.
user avatar
  • 11
1 vote
1 answer
31 views

Generate all strongly connected tournament

I want to generate all strongly connected tournament of size $n \in \{4, 11\}$. As a strongly connected tournament has an hamiltonian path I may assume that $v_i v_{i+1}$ is always an arc, and $v_n ...
user avatar
  • 75
0 votes
0 answers
51 views

Get a specific number of points from a density distribution area to minimize the average distances

Assuming that an area $A$ on the plane has a known density distribution function $\rho (x, y)\geqslant 0$, now the goal is to obtain $n$ points $p_1, p_2, ..., p_n$ on the area so that $\iint_{}^{} \...
user avatar
  • 143
1 vote
2 answers
190 views

Efficiently finding the largest divisor of N less than sqrt(N)

Suppose you have a number $$ N = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $$ and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, A060775$(N)$.) How can I efficiently find this $d$? ...
user avatar
  • 8,358
0 votes
0 answers
44 views

Impact of reducing the number of distinct elements in the Count distinct problem

I am dealing with the Count distinct problem and Space saving algorithm. The problem goes like that: I have a stream of $N$ elements. The number of distinct elements is $D$. Space saving algorithm is ...
user avatar
2 votes
1 answer
63 views

Efficient algorithm for edge-coloring complete graphs

Edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color with an optimal number of colors. Two edges are said to be adjacent if ...
user avatar
  • 982
1 vote
1 answer
259 views

Runtime for Terrible "Sorting Algorithm"?

Before I begin, I apologize for the bad wording. Consider the following "sorting algorithm": Suppose there are $n$ books on the bookshelf labeled $1$-$n$, and ordered from left to right in a ...
user avatar
7 votes
2 answers
773 views

Product of complex numbers on the unit circle with largest real part

Let $T = \{z_1, \ldots z_n\}$ be a finite set of complex numbers on the unit circle. I would like an algorithm which can quickly compute the nonempty subset $S \subset T$ which maximizes $$\left| \...
user avatar
  • 1,643
13 votes
2 answers
554 views

Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?

There are a number of criteria for determining whether a polynomial $\in \mathbb{Z} [X]$ is irreducible over $\mathbb{Q}$ (the traditional ones being Eisenstein criterion and irreducibility over a ...
user avatar
4 votes
3 answers
217 views

Algorithm to calculate edge orbits of a graph

Vertex orbits are a well-known concept in Graph Theory: these are the equivalence classes of vertices under the automorphism group $Aut(G)$ of a graph $G$. In the example, circled vertices are ...
user avatar
  • 233
6 votes
1 answer
236 views

Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$

The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...
user avatar
  • 12.8k
2 votes
1 answer
99 views

Algorithm for compact polynomial expressions

Sometimes an ugly polynomial (perhaps in several variables) can be expressed as a small sum of much simpler polynomials. Can this be done algorithmically? More precisely: Is there a reasonable ...
user avatar
1 vote
0 answers
378 views

How to describe all integer solutions to $x^2+y^2=z^3+1$?

The question is to find all integer solutions to the equation $$ x^2+y^2=z^3+1. $$ This equation obviously has infinitely many integer solutions (take, for example, $(x,y,z)=(1,u^3,u^2)$ for any ...
user avatar
3 votes
1 answer
114 views

Binary cellular automata: How slowly can an eroder remove $1$'s?

Consider some deterministic, monotonic, eroding binary cellular automata on some lattice $\mathbb{Z}^d$, and consider the set of initial states $I(L)$ in which all of the vertices are $0$ except for ...
user avatar
0 votes
1 answer
36 views

Reconstructing a 2-factor from its edge set

Let $G(V,E)$ be a symmetric graph with $n$ vertices and $m$ edges that has a $2\text{-factor}$ with edge set $F$, i.e. $F$ are the edges of an undirected vertex-disjoint cycle cover of $G$. Question: ...
user avatar
0 votes
1 answer
174 views

Louvain method: Why do they drop coefficient 1/m in the official implementation?

Intro I'm referring to the original paper Fast unfolding of communities in large networks by Blondel et al. in this question and adopt their notation. Explanation for the used symbols is on page 4 ...
user avatar
  • 103
4 votes
0 answers
163 views

Is there a polynomial time algorithm for finding primes?

I was wondering if, given $k$, there is a deterministic polynomial time algorithm (polynomial in $k$) which finds a prime number with $k$ digits. There is clearly a probabilistic one: just take random ...
user avatar
3 votes
0 answers
185 views

Conversion of proofs between HoTT and ZFC

HoTT provides a foundation of math that remains mysterious for many mathematicians including me. Hence this question. There are several implementations of math based on ZFC, an example being MetaMath. ...
user avatar
  • 4,005
0 votes
0 answers
64 views

Do there exist methods for determining the orbits of a group action on the cartesian product of sets?

Suppose that we have some group $G$ acting on some set $\Omega$. Then $G$ acts on $\Omega^n = \Omega \times \cdots \times \Omega$ ($n$ times) naturally. I wonder, is there an iterative algorithm to ...
user avatar
  • 161
2 votes
0 answers
40 views

Do there (or might there) exist computable invariants for Aut(G)-invariant subgraphs of a graph G?

I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so $$\{F|E(G)\...
user avatar
  • 161
12 votes
0 answers
232 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 ...
user avatar
2 votes
0 answers
45 views

Calculating permanents via Branch and Bound

Permanents can be interpreted as counting directed cycle covers of an asymmetric graph with unit cost edge weights. That interpretation leads to a branch and bound algorithm for calculating the ...
user avatar
1 vote
1 answer
47 views

Steiner tree subject to edge capacity constraint

Given a network of routes modeled as a graph where each edge $e$ has a capacity $c_e$. We have a source node $s$ and a set of destination nodes $t_i$ ($1\le i\le k$). We need to transport $q_i$ ...
user avatar
  • 491
1 vote
2 answers
160 views

Does having the discrete logarithm of prime factors of $n$ allow us to calculate any discrete log more efficiently?

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\...
user avatar
1 vote
0 answers
86 views

Automated, algorithmic construction of bijective proofs of combinatorial identities

Let $a_n$ and $b_n$ be two different expressions in natural $n$ with values in the set of all nonnegative integers such that we have the identity $a_n=b_n$ for all $n$. As a simplest example, we may ...
user avatar
6 votes
0 answers
187 views

Where to cut off a double sum?

I have to compute a double infinite sum to within a given accuracy $\epsilon$. Let us say the sum is of the form $$\sum_{m\geq 1} \sum_{n\geq 1} \frac{a_{m,n}}{m^2 n^2 \max(m,n)},$$ where $|a_{m,n}|\...
user avatar
  • 16.7k
2 votes
3 answers
179 views

Matrix-free linear solve for nullspace

I'm looking for an algorithm to solve for the classic: $$A\mathbf{x} = \mathbf{b}$$ I cannot compute $A$ directly, but rather can compute matrix-vector products $A\mathbf{v}$ for any $\mathbf{v}$. At ...
user avatar
1 vote
1 answer
94 views

Construct a rooted plane tree with nodes labelled

A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees. ...
user avatar
  • 982
5 votes
1 answer
138 views

Inserting points into a polygon

I want to insert $n$ points into arbitrary polygon $P$ described by ordered list of its vertexes $v_1, v_2, ..., v_m$. Each inserted point must distanced from the others on distance at least $d$. In ...
user avatar
0 votes
0 answers
67 views

Denesting of sum of multiple square roots

It was well known that a nested radical with form $\sqrt{a+b\sqrt{q}}$ can be "denested" if and only if either $a^2-b^2q$ or $q(b^2q-a^2)$ is a square. However, I can't make any ...
user avatar
1 vote
1 answer
77 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 ...
user avatar
  • 491
1 vote
1 answer
64 views

Deduce unsolvability of $\operatorname{IP}(G_0)$ from the Adian–Rabin Theorem

$\operatorname{IP}(G_0)$: the special isomorphism problem for $G_0$, i.e., given $G_0$, determine if $G$ is isomorphic to $G_0$. My question is that how can we deduce from the Adian–Rabin theorem that ...
user avatar
  • 51

1
2 3 4 5
29