Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
466
questions with no upvoted or accepted answers
20
votes
0
answers
704
views
Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?
The following question arose as a side product of some work I have been part of recently.
An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a ...
- 3,950
18
votes
0
answers
461
views
In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?
Decision Problem
Input: An $m$ by $n$ Boolean matrix $M$.
Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
- 5,065
17
votes
0
answers
1k
views
Longest geometrically increasing subsequence
Given a sorted array of $n$ positive integers, the problem is to find the longest subsequence so that the progression of differences between consecutive elements of the subsequence is geometrically ...
- 3,950
17
votes
0
answers
1k
views
Tiling a rectangle with the fewest squares
Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares.
Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best ...
- 741
16
votes
0
answers
166
views
Is it possible to boost the error probability of a Consensus protocol over dynamic network?
Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
- 211
15
votes
0
answers
454
views
Semiprime factorization, Groebner bases and a Nullstellensatz certificate
Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}...
- 537
15
votes
0
answers
1k
views
Reference request: a more complete "faster factorization into coprimes"
Some months ago, before the advent of "CS-Theory", I asked a question on MathOverflow about efficiently factoring an integer N into coprime factors n1 and n2, where n1 is a multiple of a given a ...
- 8,821
14
votes
0
answers
510
views
Is it possible to find the median with a linear size sorting network?
Is there a sorting network that makes only $O(n)$ comparisons and finds the median?
The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of ...
- 14k
14
votes
0
answers
363
views
Finding all-pairs anti-distance
Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.
Let $G=(V,E)$ ...
- 211
14
votes
0
answers
488
views
DPLL and Lovász Local Lemma
Let $\varphi$ be a CNF formula. Suppose that each of $\varphi$'s clauses consist of exactly $t$ literals (and, moreover, all literals within one particular clause correspond to different variables). ...
- 1,559
14
votes
0
answers
610
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 1,953
14
votes
1
answer
343
views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(...
- 838
14
votes
1
answer
610
views
Exact Algorithm for edge labeling problem in DAG
I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.
Problem: We are given directed acyclic graph $G=(V,E)$. ...
- 333
13
votes
0
answers
177
views
What is the curve of "search vs. insert"
Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time.
With this ...
- 369
13
votes
0
answers
196
views
Complexity to compute the eigenvalue signs of the adjacency matrix
Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like ...
- 1,346
13
votes
0
answers
177
views
Minimal rare subgraphs
I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
- 161
13
votes
0
answers
804
views
Online algorithms: open problems
Recently the long-standing k-server problem has been solved by Nikhil Bansal, Niv Buchbinder, Aleksander Mądry and Seffi Naor (to appear in FOCS 2011). I'm interested in knowing other open problems in ...
- 131
13
votes
0
answers
1k
views
What is the currently best known algorithm for the transportation problem?
Consider the well known transportation problem:
There are $m$ supply nodes, $n$ demand nodes and $k$ feasible arcs.
Every node has a integer supply or demand, and the arcs have integer costs, used ...
- 990
12
votes
0
answers
284
views
Hardness of optimal sorting
For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known.
From a purely theoretical perspective, however,
exactly optimal ...
- 1,085
12
votes
0
answers
173
views
Generating a random graph with constraints on spectrum
Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...
- 10.2k
12
votes
0
answers
362
views
Directed Sparsest Cut on Planar Graphs?
The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the ...
- 426
12
votes
0
answers
277
views
Conditional density of primes
We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem.
My question is
about the density of primes when we choose random numbers from a ...
- 21.4k
11
votes
0
answers
259
views
Computational Complexity of the Frobenius Problem
The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
- 219
11
votes
0
answers
2k
views
Which algorithm can do a stable in-place binary partition with only O(N) moves?
I'm trying to understand this paper: Stable minimum space partitioning
in linear time.
It seems that a critical part of the claim is that
Algorithm B sorts stably a bit-array of size n in
O(nlog2n) ...
- 211
10
votes
0
answers
147
views
Fastest Known Algorithm to Count Acyclic Orientations in a Graph
Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....
- 506
10
votes
0
answers
239
views
Complexity of cycle cancellation with integral capacities and irrational costs
Cycle cancellation is a standard textbook algorithm for computing minimum-cost circulations: As long as the residual graph of the current circulation contains a negative cycle, push as much flow along ...
- 23k
10
votes
0
answers
230
views
Does a polynomial-time algorithm for factoring product of two primes imply a polynomial-time algorithm for factoring in general?
Is it known if the existence of a polynomial-time algorithm for the promise problem of factoring of numbers with two prime factors implies that factoring in general has a polynomial-time algorithm?
- 101
10
votes
0
answers
135
views
Reconstructing labeled poset from linear extensions
Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
- 8,846
10
votes
0
answers
264
views
Complexity of the min edge-colored cut problem
Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is ...
- 101
10
votes
1
answer
350
views
Algorithm to compute distance between powers
Given coprime $a, b$, can you quickly compute $$ \min_{x, y > 0} |a^x - b^y| $$
Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these ...
- 261
10
votes
1
answer
493
views
Finding a cutting plane that splits a polyhedron evenly
Say we have a polyhedron in standard form:
\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}
Are there any known methods for ...
9
votes
0
answers
162
views
What are some examples of algorithmic applications of noncommutative rational identity testing?
The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.
The related problem of noncommutative rational identity testing (NCIT) is known ...
- 506
9
votes
0
answers
358
views
Complexity of $k=2$ set packing
I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem:
Given a family of subsets $S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$, ...
- 91
9
votes
0
answers
135
views
Purely Functional Representations of Catenable Sorted Lists question
Good day.
I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists" by Tarjan and Kaplan[link to the paper]. But I have a question
about the modified 2-3 finger ...
- 303
9
votes
0
answers
559
views
Is it possible to solve perfect matching in linear time
As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft.
Is it possible to solve perfect matching problem in linear time for given $...
- 99
9
votes
0
answers
368
views
Maximum local edge connectivity
For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
- 4,367
9
votes
0
answers
306
views
Additive error in counting the number of 1's in a sliding window?
The setting is as follows:
We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
- 9,428
9
votes
0
answers
123
views
Computing weighted sums of binomial coefficients
This question is a reformulation of
Complexity for computing weighted number of paths on integer lattice
Is there any way to compute in $o(n^2)$ all $n$ sums
$\sum_{0\leq i \leq j} a_i\binom{j}{i}$ ...
- 1,085
9
votes
0
answers
630
views
Fundamental assumptions in complexity analysis
I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as RAM....
- 191
9
votes
0
answers
569
views
Finding SVD efficiently for $AB^T$
I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ and $B$ separately)
EDIT: (I have added the second question here since it was closed as a ...
user4292
8
votes
0
answers
175
views
Is Gödel's speed-up theorem an instance of Blum's speedup theorem?
Blum's speedup theorem is a statement about a certain class of computable functions for which it is always possible to find a faster algorithm.
Gödel's speed-up theorem is a statement about the ...
- 214
8
votes
0
answers
137
views
Finding $n$ many different primes efficiently
I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many ...
- 420
8
votes
0
answers
303
views
Algorithms to generate consecutive primes
The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates ...
- 20.8k
8
votes
0
answers
184
views
Speed-up of Boolean over Algebraic computation
I would like to know what is the maximum speed-up of algebraic computation when we work in the word RAM model.
This question is motivated by this theorem from Ryan's paper:
Theorem 1.2 Let $(R, +, ...
- 1,130
8
votes
0
answers
172
views
Is 4-colors precoloring extension for planar graphs fixed parameter tractable?
Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable).
Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
- 9,428
8
votes
0
answers
4k
views
Time complexity of a branching-and-bound algorithm
Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
- 854
8
votes
0
answers
713
views
Efficient Reduction from Min Cut to st-Min Cut
I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut.
But the question of efficient reduction from min cut to $st$-min cut is still interesting to ...
- 1,130
8
votes
0
answers
113
views
Computing the most likely winner in elections : intermediate case between Kemeny and Borda?
Given
$n$ possible alternatives satisfying some unknown linear ordering,
a multiset of pairwise votes, i.e., a matrix $M\in\mathbb{N}^{n\times n}$:
$M_{i,j}$ counts the number of votes for which $i&...
- 1,085
8
votes
0
answers
207
views
Simplifying the disjoint union of wildcard strings
Setting: patterns with "don't care" symbols, binary alphabet.
For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$.
We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) ...
- 11.5k
8
votes
0
answers
198
views
Complexity of checking if AB intersects C
Let $A,B,C$ be subsets of a nonabelian group $G$,
and assume we know the structure of $G$ "fairly well"
(e.g., $G = S_n$ or $A_n$).
Assume that group operations take $O(1)$ time.
Is it ...
- 3,243