# 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,190 questions
Filter by
Sorted by
Tagged with
172 views

### Solving multilinear equations

Let $N=\{1,2,\ldots,n\}$. Suppose we are given $n$ equations, with each equation taking the form $\sum_{A\subseteq N}\left(c_A \prod_{i\in A}x_i \right) = 0$, where each $c_A$ is a real number ...
24 views

### Finding minimum weight perfect matchings in sparse bipartite graphs

Question: What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values? I am looking for ...
107 views

### Integrality certification for product of two matrices $A B^{-1}$

Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular ...
16 views

### Search Algorithm in d-D Tucker

The algorithm of search a complementary edge in TUCKER seems to need at most O(n^2) time complexity. How to query with fewer vertices?
56 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 ...
10 views

### Finding weight minimal swap-free directed vertex covers

Suppose a complete directed graph is given with $n$ vertices and $n(n-1)$ weighted arcs $a_{ij}$ and we have $\omega(a_{ij}\ne\omega{a_{ji})$ for at least one pair of antiparallel arcs and the ...
274 views

1k views

### Shift and sort the sequence

Given a permutation of integers $1$ through $N$, we need to determine whether it is possible to sort this list in an increasing order by following certain conditions. The conditions imposed are : We ...
115 views

### Minimum number of swaps needed to 'group' a sequence?

Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...
25 views

### Enumerating all directed 3-cycle covers

It is fairly easy to enumerate the directed Hamilton cycles of a complete directed graph by fixing one of the vertices and enumerating the permutations of the others via one of the next-permutation ...
96 views

12 views

### Statistics of trees in vertex-covering forests

What can be said about the properties of graphs $F$ that are generated from the edges of complete symmetric graphs $G(V,E)$ in the following way: fix an enumeration process for the edges in $E$ ...
256 views

### Transfinite algorithms

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
180 views

### Explicit construction of the Jacobian of a curve

Let $k$ be an algebraically closed field (of arbitrary characteristic), and $C$ a smooth projective curve over $k$, given by defining equations in projective space. I am looking for an algorithmic ...
43 views

69 views

### Random sparse and invertible matrices

Let $n\leq m$ and $0\leq k\leq (n\times m - \min\{n,m\})$ be in $\mathbb{N}$. Let $\mu$ be a probability measure dominated by the Lebesgue measure on $\mathbb{R}$ and generate a random $n\times m$ ...
22 views

### Complexity of combined trajectory compression algorithm

Is it possible to calculate the complexity of the combined algorithms (TD-TR-SP, TD-SP-TR) provided here: A new perspective on trajectory compression techniques In more details, TD-TR-SP algorithm ...
25 views

### balls and boxes optimization

There are $n$ balls, among which $m$ balls are bad, and hence $n-m$ are good. We are given a number of boxes. We want to put balls into boxes such that all the good balls (or most of them, e.g., $99$%)...
296 views

116 views

### Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$

Given a natural number $n$ (of unknown factorization) and an arbitrary number $c \in \mathbb{Z}^*_n$ (the set of natural numbers smaller than $n$ and coprime to it), is there an efficient algorithm ...
46 views

### 3-uniform hypergraphs and their circuit space

So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...
19 views

### Calculating graph connectivity faster

this is a followup question to Identifying the edges that are essential for biconnectivity: consider a vertex-split graph $G(V,E)$ in which every vertex of a vertex-cut of size $k$ is adjacent to an ...
103 views

### summation of oscillating functions

Consider series of the form $S=\sum_{n\ge1}f(n)P(n)$, where $f$ is some smooth function, and $P$ is a periodic or quasi-periodic function (e.g., $P$ can be a trigonometric function, so $S$ a Fourier ...
63 views

### Identifying the edges that are essential for biconnectivity

Question: If $G(V,E)$ is a biconnected symmetric graph, is it possible to identify the edges, whose deletion destroys biconnectivity, in the following way: determine the union $B:= ST\cup F_1$ of ...
77 views

### Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

Let $G$ be connected simple graph. Clique cover of graph $G$ is partition of the vertices of $G$ into $k$ disjoint cliques $D'_i$. Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle in ...
480 views

### Optimization algorithm sought

Suppose I have $N$ pairs of positive numbers $(a_1, b_1), (a_2, b_2), \dotsc, (a_N, b_N).$ and I want to find a subset of $M$ of them maximizing $$\frac{\sum_{j=1}^M a_{i_j}}{\sum_{j=1}^M b_{i_j}}.$$...
107 views

### Finding a cycle of a specific length in an edge-weighted graph

I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph. For example, imagine my phone tells me that I need to walk three miles today. It ...
35 views

### maximum weighted matching with weights being sets

Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...
25 views

### Computational complexity of higher order orthogonal iteration for Tucker decompositions

I am currently doing background reading for my Masters Thesis. I am working with tensor decompositions, where by tensor I simply mean a multi-dimensional array. The aim of my masters project is to ...
145 views

### Algorithm for reporting all triangles with unique interior point

What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...
173 views

### Freedom problem in hyperbolic groups

I will start with a general algorithmic question: Question. (A faithfulness decision problem.) Suppose that $G, H$ are finitely-presented groups with decidable word problem. Is injectivity decidable ...
90 views

Given a planar polygonal linkage defined by a sequence of $n$ hinge joints $(j_0,\,\cdots,\,j_{n-1},j_n = j_0)$ with links of fixed lengths $\lbrace\|j_{k+1}-j_k\|=d_k\ |\ 0\le k\lt n\rbrace$ between ...
227 views

### Algorithm to generate free unlabelled trees uniformly at random

I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
90 views

### Calculating the values of a generalization of binomials to permutations

let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...
85 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 ...
72 views

### a probability density algorithm that is not sensitive to the initial condition

There are many algorithms to estimate the density of probability distributions. I am looking for one that is not sensitive to the initial condition. For instance, Expectation–maximization algorithm ...
69 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 ...
66 views

### Algorithm to compute minimal polynomials

Suppose $L/K$ is a finite Galois extension of fields of degree $n$. Suppose that we know an irreducible polynomial $f\in K[x]$ such that $L\cong K[x]/(f)$. Suppose also that we know the Galois group ...