Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
465
questions with no upvoted or accepted answers
5
votes
0
answers
137
views
Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound
I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are ...
- 12.8k
4
votes
0
answers
95
views
$\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?
Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that
$$\log_a^\star (a \uparrow \uparrow b) = b$$...
- 2,121
4
votes
0
answers
195
views
Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover
Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
- 576
4
votes
0
answers
86
views
Flipping one bit to maximize BMM output
Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative ...
- 1,177
4
votes
0
answers
89
views
Complexity of Encoding a Matroid Flow Problem in a Matrix
Context:
Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$.
We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
- 576
4
votes
0
answers
313
views
Deciding whether $2^k+m$ is prime
I thought something fancy can be done with number-theory or memoization, but neither worked for me. Being limited in knowledge I decided to ask experts.
Does there exist a deterministic polynomial-...
- 149
4
votes
0
answers
207
views
On solving Planar Circuit SAT
This enquiry is three-sided.
Side 1 - State of the art
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$?
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
- 6,782
4
votes
0
answers
204
views
What's the fastest known algorithm for finding the diameter of a graph?
Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?
- 195
4
votes
0
answers
143
views
2-hop distributed coloring in the CONGEST model
Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$.
A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
- 9,438
4
votes
0
answers
211
views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
- 235
4
votes
0
answers
1k
views
Optimizing Maximum Weighted Matching (Edmonds Blossom)
Background:
I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java:
https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java
The original Python implementation ...
- 231
4
votes
0
answers
98
views
How to construct an $(n,m,k)$ ``separating set''?
This problem is probably known under some other name, if anyone has seen it before, a reference will be great.
Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary ...
- 9,438
4
votes
0
answers
292
views
Voronoi diagram in presence of polygonal obstacle
Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$.
The distance between a point $p \in ...
- 1,006
4
votes
0
answers
71
views
Constructing a bad sequence for counter algorithm
Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'.
The sequence is then feed to the following probabilistic algorithm:
...
- 9,438
4
votes
0
answers
289
views
Bit complexity of modulo operations?
We know that using FFT we can compute multiplication of an $a$ bit number with a $b$ bit number in $(a+b)^{1+\epsilon}$ time.
My question is supposing we want to compute $A\bmod B$ where $A$ is an $a=...
- 12.8k
4
votes
0
answers
93
views
Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs
Let $G=(V, E)$ be an undirected simple graph.
Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space ...
- 650
4
votes
0
answers
177
views
Complexity of a naive algorithm for finding the longest Fibonacci substring
I already posted this question here but I didn't receive an answer, so I'm posting it here as well :)
Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:
...
- 151
4
votes
0
answers
178
views
Problems in dynamic algorithms in computational geometry
The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as:
Dynamic ...
- 313
4
votes
0
answers
75
views
How many exponentiations can the Shamir algorithm reduce?
The Shamir's algorithm is depicted as follows (cited from
Handbook of Applied Cryptography, chapter 14, algorithm 14.88, page 618)
Shamir's algorithm
INPUT: group elements $g_0,g_1,\dots, g_{k-1}$ ...
- 41
4
votes
0
answers
251
views
What is known about finding heavy hitters in a sliding window?
This question is strongly related to another question I asked here a few weeks ago.
In this problem setting we have a stream of elements $s_1,s_2,...$, such that $\forall i: s_i\in \mathcal X$ for ...
- 9,438
4
votes
1
answer
1k
views
Knapsack with dependent profits (pairs of items)
I'm working on a problem which MAY be reduced to the following version of Knapsack:
Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
- 157
4
votes
0
answers
104
views
Constructing a small (n,k)-Covering Matrices family
Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$.
We call ${\cal A}$ a (n,k)-covering, if for every subset of columns
$I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in {\...
- 9,438
4
votes
0
answers
272
views
Heuristic algorithm design techniques
I am looking for a good relatively complete and up-to-date book or survey about heuristic algorithm design techniques.
- 21.5k
4
votes
0
answers
115
views
Computing a frontier set for some Boolean-valued function in a lattice?
Assume that we have a non-empty finite lattice $(L,\leq)$ and a monotone Boolean-valued function $f : L \rightarrow \mathbb{B}$ (i.e, for every $x,y \in L$, if $f(x)=\mathbf{true}$ and $x \leq y$, ...
- 264
4
votes
0
answers
389
views
The number of maximal subsets with sum less than $m$
I've met this problem.
I would like to know to which complexity class it belongs.
Input
a set of positive integers $I$,
an integer $m$,
an integer $n$.
Question
Is the number of $S \subseteq I$ such ...
- 141
4
votes
0
answers
156
views
Find index set partition that has large projections
I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of $\{1,2,\dots,n\}$...
- 11.7k
4
votes
0
answers
510
views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
- 141
4
votes
0
answers
1k
views
How to determine proper rounding in linear programming relaxations?
Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such ...
- 141
4
votes
0
answers
665
views
What about apply maxplus algebra for all-pairs shortest paths?
I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know ...
4
votes
0
answers
117
views
Approximating Front Size of Asymmetric Matrices
The front size of a matrix $A$ is the largest number of non-zeros below the diagonal in any column of its Cholesky factor. If $A$ is symmetric then the minimum front size of $A$ is equal to the ...
- 10.6k
4
votes
0
answers
233
views
Triangulation with maximum greatest area
Given a point set $P$ and a triangulation $T$ of $P$ with $d$ triangles, let's define
$$\alpha(T) = (\alpha_1, \alpha_2, \ldots, \alpha_{3d})$$
which denotes the series of interior angles of $T$, ...
4
votes
0
answers
332
views
Problem with bitwise AND/OR on binary strings
Let $W = \{s_1, s_2, \ldots, s_n\}$ be a set of $m$-length binary strings and let $\land$ and $\lor$ be the binary operators of bitwise AND and OR. A bitwise formula $\phi$ is composed of operands in $...
- 1,443
4
votes
0
answers
327
views
Time complexity for solving linear congruences?
What is the best known algorithm to solve linear congruences of the form below?
$$a x + b \equiv 0 \space (n)$$
And what is the time complexity of it?
- 41
4
votes
0
answers
478
views
worst case external fragmentation in buddy memory systems
Unfortunately, I can't find any freely available text with an estimation of exact upper bound of (external) fragmentation overhead for (binary) buddy memory allocator. Estimation $M(1+ \log 2 m)$ (...
- 206
4
votes
0
answers
245
views
Ising Model and Eulerian Subgraphs
Let $\mathcal{X}= \{1,-1\}^n$, $E$ the set of edges and $J$ some real-valued matrix. Van der Waerden's theorem gives constant $c$ and set of edge weights such that
$$\sum_\mathbf{x\in \mathcal{X}} \...
- 4,681
4
votes
0
answers
231
views
Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?
I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
- 4,681
3
votes
0
answers
83
views
Is the Moser-Tardos algorithm used in any real-world applications?
The Moser-Tardos algorithm can be used to construct algorithms for certain combinatorial problems. However, I'm curious about whether this algorithm is utilized in real-world systems (a SAT solver, ...
- 31
3
votes
0
answers
98
views
Why do some problems seem to admit a richer family of algorithms than others?
Let's take integer multiplication and comparison sorting as examples. Despite being roughly comparable in terms of computational complexity, if we look at the set of algorithms which solve each ...
- 803
3
votes
0
answers
105
views
Linear time in-place stable sort
Surprisingly, linear time in-place stable sort is possible with integer keys of $O(\log n)$ bit length.
An algorithm appeared in Radix Sorting With No Extra Space (Franceschini, Muthukrishnan, ...
- 2,537
3
votes
0
answers
55
views
Counting subsets of bipartite graph part which admit an induced perfect matching
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
3
votes
0
answers
618
views
Time Complexity for Nearest Neighbor Searches in kd-trees
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of ...
- 131
3
votes
0
answers
124
views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
- 603
3
votes
0
answers
43
views
Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
- 131
3
votes
0
answers
195
views
How to write algorithms?
Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
user45424
3
votes
0
answers
95
views
Lower bound for reversing a list using queues
How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues?
Each queue is FIFO. Time refers to the number of operations on the queues.
...
- 2,537
3
votes
0
answers
223
views
Fast way of getting a matrix of sums
We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a ...
- 2,100
3
votes
0
answers
125
views
Graph-related applications of the fast Fourier transform (and other algebraic algorithms)
The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths).
However, while the fast Fourier transform algorithm implies several other near-...
- 1,130
3
votes
0
answers
68
views
Is there some research about infinitely many-armed bandit with non-stationary assumption?
Is there some research about infinitely many-armed bandit with non-stationary assumption? I have found the paper about infinitely many-armed bandit under stationary (or stochastic) assumption. And I ...
- 31
3
votes
0
answers
605
views
Convention for RAM machine models
When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used?
My understanding is that most problems use unit-cost ...
- 2,537
3
votes
0
answers
370
views
Complexity of the mandelbrot set on rationals
(Also posted on mathoverflow) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals.
A point $c$ is contained within the Mandelbrot ...
- 1,132