Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

436 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
20 votes
0 answers
696 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 ...
user avatar
  • 3,920
18 votes
0 answers
447 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 ...
user avatar
17 votes
0 answers
923 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 ...
user avatar
  • 3,920
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 ...
user avatar
16 votes
0 answers
165 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 ...
user avatar
  • 211
15 votes
0 answers
447 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}...
user avatar
  • 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 ...
user avatar
14 votes
0 answers
471 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 ...
user avatar
  • 13.5k
14 votes
0 answers
360 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)$ ...
user avatar
  • 211
14 votes
0 answers
479 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). ...
user avatar
  • 1,559
14 votes
0 answers
559 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 ...
user avatar
  • 1,933
14 votes
1 answer
342 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 $(...
user avatar
  • 838
14 votes
1 answer
606 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)$. ...
user avatar
  • 333
13 votes
0 answers
174 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 ...
user avatar
13 votes
0 answers
192 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 ...
user avatar
  • 1,346
13 votes
0 answers
758 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 ...
user avatar
  • 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 ...
user avatar
12 votes
0 answers
278 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 ...
user avatar
  • 1,085
12 votes
0 answers
164 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 ...
user avatar
12 votes
0 answers
172 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 ...
user avatar
  • 151
12 votes
0 answers
343 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 ...
user avatar
12 votes
0 answers
275 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 ...
user avatar
  • 21.3k
11 votes
0 answers
239 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+\...
user avatar
  • 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) ...
user avatar
  • 211
10 votes
0 answers
128 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....
user avatar
  • 454
10 votes
0 answers
231 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 ...
user avatar
  • 22.8k
10 votes
0 answers
224 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?
user avatar
  • 101
10 votes
0 answers
129 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 ...
user avatar
  • 7,455
10 votes
0 answers
243 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 ...
user avatar
  • 101
10 votes
1 answer
342 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 ...
user avatar
  • 261
10 votes
1 answer
478 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
151 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 ...
user avatar
  • 454
9 votes
0 answers
132 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 ...
user avatar
  • 303
9 votes
0 answers
553 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 $...
user avatar
  • 99
9 votes
0 answers
347 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 ...
user avatar
  • 4,256
9 votes
0 answers
291 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 ...
user avatar
  • 9,378
9 votes
0 answers
122 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}$ ...
user avatar
  • 1,085
9 votes
0 answers
414 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....
user avatar
  • 191
9 votes
0 answers
557 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 ...
user avatar
8 votes
0 answers
147 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 ...
user avatar
  • 189
8 votes
0 answers
134 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 ...
user avatar
  • 420
8 votes
0 answers
288 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 ...
user avatar
8 votes
0 answers
345 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\}$, ...
user avatar
  • 81
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, +, ...
user avatar
  • 1,120
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 ...
user avatar
  • 854
8 votes
0 answers
671 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 ...
user avatar
  • 1,120
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&...
user avatar
  • 1,085
8 votes
0 answers
202 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) ...
user avatar
8 votes
0 answers
190 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 ...
user avatar
8 votes
0 answers
480 views

Nuts and Bolts problem: Simpler $o(n^2)$ algorithm

In this paper, the authors mention that it is possible to get an $o(n^2)$-time algorithm for the nuts and bolts problem by choosing samples based on a projective plane. They also mention that a non-...
user avatar
  • 401

1
2 3 4 5
9