Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
412
questions with no upvoted or accepted answers
21
votes
0answers
678 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 ...
21
votes
0answers
836 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 ...
18
votes
0answers
393 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 ...
17
votes
0answers
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 ...
15
votes
0answers
158 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 ...
15
votes
0answers
408 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 ...
15
votes
0answers
438 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}...
15
votes
0answers
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 ...
14
votes
0answers
307 views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
14
votes
0answers
351 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)$ ...
14
votes
0answers
2k views
minimizing size of regular expression
Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do ...
14
votes
0answers
459 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). ...
14
votes
0answers
511 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 ...
14
votes
1answer
340 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 $(...
14
votes
1answer
584 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)$. ...
13
votes
0answers
171 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 ...
13
votes
0answers
366 views
Can we approximate the number of words accepted by an NFA?
Let $M$ be an acyclic NFA.
Since $M$ is acyclic, $L(M)$ is finite.
In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete.
The second ...
13
votes
0answers
189 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 ...
13
votes
0answers
714 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 ...
13
votes
0answers
934 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 ...
12
votes
0answers
254 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 ...
12
votes
0answers
168 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 ...
12
votes
0answers
335 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 ...
12
votes
0answers
269 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 ...
11
votes
0answers
207 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+\...
11
votes
0answers
158 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 ...
11
votes
1answer
336 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 ...
10
votes
0answers
212 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 ...
10
votes
0answers
223 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?
10
votes
0answers
125 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 ...
10
votes
1answer
1k views
Count $k$-hop neighborhood for every vertex
For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ ...
10
votes
0answers
235 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 ...
10
votes
0answers
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) ...
10
votes
1answer
457 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
0answers
128 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 ...
9
votes
0answers
139 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 ...
9
votes
0answers
133 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 ...
9
votes
0answers
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 ...
9
votes
0answers
499 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 $...
9
votes
0answers
334 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 ...
9
votes
0answers
259 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
votes
0answers
121 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}$ ...
9
votes
0answers
387 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....
9
votes
0answers
544 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 ...
8
votes
0answers
263 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 ...
8
votes
0answers
322 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\}$, ...
8
votes
0answers
126 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 ...
8
votes
0answers
182 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, +, ...
8
votes
0answers
541 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 ...
8
votes
0answers
109 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&...
