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
5
votes
2
answers
446
views
Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$
Let $G = \langle V, E \rangle$ be an undirected, connected and weighted multigraph, with the weights given by a function $w: E \rightarrow N$. Consider any spanning tree $T$. Denote the edges of $T$ ...
- 161
3
votes
0
answers
111
views
How to compute image of boolean function
I have a function $F: \{0,1\}^n \to \{0,1\}^n$. Denote by $F_i : \{0,1\}^n \to \{0,1\}$ the $i$th component. I assume that for each $i$, $F_i$ can be written as conjunction of at most $n$ ...
- 283
1
vote
0
answers
49
views
Subset with largest information gain [closed]
I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$. I submit $S \subset U$, ...
1
vote
0
answers
192
views
Construction of regular hypergraphs
Is there any algorithm to generate $3$-uniform $k$-regular hypergraphs with $n$ vertices? Any help is appreciated.
- 6,001
4
votes
1
answer
1k
views
Under what conditions does an Integer Programming problem run in polynomial time?
Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
CommunityBot
- 1
0
votes
1
answer
450
views
Coloring graph with maximum vertex degree $< k$ so every vertex is a starting point for a path containing each color
Given an undirected graph ($V$ vertices, $E$ edges) with maximum vertex degree $< k$ I want to find a vertex coloring using exactly $k$ colors so that no two adjacent vertices have the same color ...
- 6,001
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
6
votes
1
answer
558
views
Variant of Graph coloring
This is a problem came from social network analysis.
In a vertex colored (need not be proper) graph, an edge is monochromatic, if both endpoints of the edge are colored with the same color. Given a ...
- 18.4k
13
votes
2
answers
660
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 1,073
0
votes
1
answer
66
views
Calculating a Measure of the Geometric Complexity of Planar Closed Polylines
Let $\lbrace p_1,\ \dots,\ p_n\rbrace$ be a set of points in the Euclidean plane and let $T_0 :=\left(p_1,\ \dots,\ p_n,p_1\right)$ be a Hamilton cycle through the set of points.
Question:
...
- 5,380
1
vote
1
answer
212
views
Matrix golf puzzle: enumerate a series by matrix multiplication
It is super easy to find matrices $X_0$, $F$ and $H$ such that $H F^n X_0$ is equal to $n$-nth element of the sequence $0,1,0,1,0,1,0,1,0,1,0,1,...$
Maybe it is a slightly harder challenge to find ...
- 22.2k
4
votes
1
answer
278
views
Small roots of $f(x) \equiv 0 \pmod{n^2}$
Let $f(x)$ be squarefree polynomial with integer coefficients.
For integer $n$ define "small root modulo $n^2$" integer $a$
satisfying $1 \le a \le n$ and $f(a) \equiv 0 \pmod{n^2}$ and
$f(a) \ne 0$.
...
- 30k
1
vote
1
answer
383
views
Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?
Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ are irreducible and of equal degree what is the best ...
CommunityBot
- 1
2
votes
3
answers
1k
views
Finding integer representation as difference of two triangular numbers
Since $n = \frac{n(n+1)}{2}-\frac{n(n-1)}{2}$, every natural number can be represented as the difference of two triangular numbers:
$ n = \frac{a(a+1)}{2}-\frac{b(b-1)}{2}$. Finding such a ...
- 1
0
votes
1
answer
179
views
Bound on queries to a tree with unusual probabilties -- follow-up
This question follows up on Bound on queries to a tree with unusual probabilities, where @fedja was able to disprove my conjecture under only constraints (1-4) below. I restate the relevant facts here ...
- 209
7
votes
1
answer
219
views
Bound on queries to a tree with unusual probabilities
Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\...
- 209
3
votes
1
answer
293
views
Nearest trio of neighbours for non-intersecting ellipses
I'm working on a problem which is to find the closest trio of neighbours for a set of arbitrarily placed non-intersecting ellipses. As a new user I'm not allowed to include image tags but I've ...
- 149k
3
votes
0
answers
174
views
Testing two algebras for isomorphism
Given two finite dimensional algebras over a finite field. What is the fastest algorithm to check wheter they are isomorphic ? As far as I know there is no such algorithm yet in GAP, which might ...
- 26.1k
3
votes
0
answers
99
views
Are there scenarios under which feasibility bilinear programming is easy?
Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
- 13.7k
1
vote
0
answers
88
views
On convex quadratic programming clarification
We know convex quadratic programming is in $P$.
Is it also in $P$ if the function of interest is only convex in the domain of interest?
- 13.7k
10
votes
2
answers
603
views
When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?
To ask this question in a (hopefully) more direct way:
Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ (i.e....
- 13.5k
3
votes
0
answers
80
views
Find four sets of coins with similar weights
There are $n\geq 4$ coins. You are allowed to ask for the weight of any set of coins. What is the worst-case (asymptotic) minimum number of questions after which you can divide the coins into four ...
- 1,199
1
vote
0
answers
271
views
How to implement the red-black ordering for any linear equation system?
I'm trying to solve linear equations systems using iterative methods, the method that i'm using is Gauss-Seidel, but i'm trying to parallelize the algorithm. I've found a method called red-black ...
- 11
2
votes
1
answer
89
views
Generating Convex Polygonal Neighborhoods from Triangulations of Discrete Pointsets
The wellknown Delaunay Triangulation $DT$ has as a straight line dual the also wellknown Voronoi Diagram $VD$.
Both are most commonly defined in the Euclidean plane and are primarily beneficial for ...
CommunityBot
- 1
6
votes
1
answer
496
views
Algorithm to compute Matrix Sign Rank?
The (generalised) sign-rank of a (generalised) sign pattern $S\in \{+,-,0\}^{n\times m}$
is the minimum rank of all matrices with the same sign pattern, i.e.
$$
\min\left\{\operatorname{rank}(M)\ :\ M\...
CommunityBot
- 1
10
votes
1
answer
670
views
Building a polyhedron from areas of its faces
Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
- 149k
1
vote
1
answer
125
views
How do I find solutions of a quadratic Diophantine equation mod a large composite?
I'd like to find integral solutions to the equation
$2x^2 -3xy + y^2 \equiv 0 \mod n $
where $n$ is a given composite, for example, $n = 16807708473783470801$ (I prefer solutions that work for any $...
- 103k
3
votes
2
answers
617
views
Covering a sphere using reflections of an intersection of three lunes
I have been trying to figure this problem out for a while, and while I believe someone must have figured it out hundreds of years ago, I still can't quite get it.
Suppose we have a 3-dimensional ...
- 149k
6
votes
0
answers
203
views
Longest string with all unique substrings
All substrings of length 2 of the binary string $1011$ are unique, as well as all 2-substrings of $10011$. 5 seems to be the longest possible string with all unique 2-substring.
$000101100$ is a ...
- 3,554
33
votes
3
answers
6k
views
Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...
1
vote
1
answer
290
views
Tutte's Reduction of Minimum Weight d-Factors to Matching
I am currently interested in minimum weight regular d-spanners (i.e. d-factors) of complete graphs. When searching the internet for related articles, I came across this one, which is concerned with ...
- 7,775
-2
votes
1
answer
330
views
Polygon Problem [closed]
There are $N$ regions which are numbered from $1$ to $N$. Each region is represented by a single simple polygon on the 2D plane. Simple polygon means the boundary of the polygon does not cross itself. ...
- 149k
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
CommunityBot
- 1
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 ...
- 2,951
5
votes
1
answer
2k
views
Intersections of quadratic planes as elliptic curves
An elliptic curve defined over a field $k$ is a smooth projective curve of genus $1$, plus a $k$-rational point. Every elliptic curve can be written in a Weierstrass form, i.e. as a plane cubic curve ...
- 20.5k
1
vote
1
answer
111
views
Optimal "Generalization" of Polylines
This question is inspired by a lossy compression technique for polylines, namely to identify a subset of the points of polyline $\mathcal{P}$, whose removal yields a polyline $\mathcal{Q}$ within a ...
- 149k
1
vote
1
answer
328
views
Finding a subgraph of cliques with the minimum total sum weight
Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty ...
- 113
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{...
- 31
1
vote
1
answer
109
views
What is a good method for computing the $N$-dimensional volume of a subset of a spherization of a cone?
I have a pointed polyhedral cone $C$ in $\mathbb{R}^{N+1}$, with the vertex at the origin. Cone $C$ is known to be the intersection of $2 (^{N+1}_{\; \;2})$ closed half-spaces.
Furthermore, there is ...
CommunityBot
- 1
20
votes
8
answers
4k
views
Determine if circle is covered by some set of other circles
Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius $r$...
- 149k
29
votes
1
answer
941
views
Is this BBP-type formula for $\ln 257$ and $\ln 65537$ true?
We have the known BBP(Bailey–Borwein–Plouffe)-type formulas,
$$\ln3 = \sum_{n=0}^\infty\frac{1}{2^{2n}}\left(\frac{1}{2n+1}\right)$$
$$\ln5 = \frac{1}{2^2}\sum_{n=0}^\infty\frac{1}{2^{4n}}\left(\...
- 23.9k
1
vote
0
answers
39
views
Optimal Encoding of Sets with DeBruijn-likeSequences
A DeBruijn sequences of order $n$ encodes all possible strings of length $n$ over an alphabet with $k$ symbols and algorithms for their construction are well known among those familiar with the ...
CommunityBot
- 1
2
votes
1
answer
462
views
Are there any solvers to Chance Constrained Programming Problems
I'm trying to solve a chance constrained programming (CCP) problem
$\min_x f_0(x, \xi), \text{ such that } \mathbb{P} ( f_i(x, \xi) \ge \alpha_i ) \le \epsilon_i, \text{ where } i = 1,2,\cdots, m$
...
- 13k
18
votes
0
answers
564
views
What is the geometric intuition behind Wilf-Zeilberger theory?
This problem is somehow inspired by a bunch of impressive posts of combinatorial identities by T. Amdeberhan. Earlier this month I learnt from computer scientists that they have a generic algorithmic ...
- 4,210
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
11
votes
2
answers
546
views
Identifying a group without 2-torsion
Suppose we have a finitely presented group $G$ with solvable word problem. (For instance, the command RWSGroup in Magma terminates giving us a finite [but possibly gigantic] rewrite system.) Is there ...
- 36.4k
2
votes
1
answer
130
views
Fast algorithm for large-scale, asymmetric transportation linear program
I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the ...
CommunityBot
- 1
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?
- 4,618
1
vote
0
answers
42
views
Matching timestamped GPS points to a path that has no timestamps [closed]
I have two data sources available - one is timestamped GPS points, and another is a path fitted to roads, without timestamps (although points are ordered).
What I need is to combine the data sources ...
- 203
1
vote
0
answers
207
views
Testing Randomness of Permutation Sequences
Maybe this question is too simple, but I couldn't find anything that is concerned with measuring how random a sequence of permutations of $n$ elements( w.l.o.g. of the numbers $\lbrace 1,\ \dots,\ n \...
CommunityBot
- 1