Skip to main content
The 2024 Developer Survey results are live! See the results

Questions tagged [ds.algorithms]

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

480 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
20 votes
0 answers
706 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 ...
Simd's user avatar
  • 3,902
18 votes
0 answers
469 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 ...
Michael Wehar's user avatar
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 ...
Simd's user avatar
  • 3,902
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 ...
randomizer's user avatar
16 votes
0 answers
169 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 ...
Irvan's user avatar
  • 211
15 votes
0 answers
459 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}...
mkatkov's 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 ...
Niel de Beaudrap's user avatar
15 votes
1 answer
614 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)$. ...
user5153's user avatar
  • 343
14 votes
0 answers
524 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 ...
domotorp's user avatar
  • 14.1k
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)$ ...
siravan's user avatar
  • 211
14 votes
0 answers
493 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). ...
ilyaraz's user avatar
  • 1,569
14 votes
0 answers
625 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 ...
Akash Kumar's user avatar
  • 1,983
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 $(...
Rachit's user avatar
  • 838
13 votes
0 answers
178 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 ...
Sidharth Ghoshal's user avatar
13 votes
0 answers
197 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 ...
Dimitris's user avatar
  • 1,356
13 votes
0 answers
181 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 ...
Artem Kaznatcheev's user avatar
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 ...
Raphael's user avatar
  • 161
13 votes
0 answers
825 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 ...
mee's 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 ...
Riko Jacob's user avatar
12 votes
0 answers
288 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 ...
Joseph Stack's user avatar
  • 1,095
12 votes
0 answers
365 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 ...
Thang Dinh's user avatar
12 votes
0 answers
278 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 ...
Kaveh's user avatar
  • 21.7k
11 votes
0 answers
280 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+\...
Alexis's 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) ...
AShelly's user avatar
  • 211
11 votes
1 answer
726 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 program of lower complexity. Gödel's speed-up theorem is a statement about ...
Rexcirus's user avatar
  • 244
10 votes
0 answers
160 views

Fine-grained complexity for game-type problems

My specific question is the following. Consider the following problem that I call Strange-TQBF: there is a Boolean function $f(x_1, \ldots, x_n)$ and two players Alice and Bob. They take turns ...
Alexey Milovanov's user avatar
10 votes
0 answers
160 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....
Naysh's user avatar
  • 686
10 votes
0 answers
243 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 ...
Jeffε's user avatar
  • 23.2k
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?
eof's user avatar
  • 101
10 votes
0 answers
138 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 ...
a3nm's user avatar
  • 9,667
10 votes
0 answers
270 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 ...
richard's user avatar
  • 101
10 votes
1 answer
352 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 ...
Gautam's user avatar
  • 261
10 votes
1 answer
500 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
170 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 ...
Naysh's user avatar
  • 686
9 votes
1 answer
339 views

Positive cut algorithm on bipartite graphs with negative weights

Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
curl-up's user avatar
  • 91
9 votes
0 answers
359 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\}$, ...
Manashi's user avatar
  • 91
9 votes
0 answers
137 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 ...
rbtrht's user avatar
  • 303
9 votes
0 answers
561 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 $...
juna's user avatar
  • 99
9 votes
0 answers
376 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 ...
Chao Xu's user avatar
  • 4,499
9 votes
0 answers
308 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 ...
R B's user avatar
  • 9,478
9 votes
0 answers
125 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}$ ...
Joseph Stack's user avatar
  • 1,095
9 votes
0 answers
631 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....
simeonz's user avatar
  • 191
9 votes
0 answers
572 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
138 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 ...
old's user avatar
  • 420
8 votes
0 answers
315 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 ...
Mohammad Al-Turkistany's user avatar
8 votes
0 answers
368 views

What exactly did Lenstra prove on mixed integer linear program?

I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
Turbo's user avatar
  • 13.1k
8 votes
0 answers
185 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, +, ...
Thatchaphol's user avatar
  • 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 ...
R B's user avatar
  • 9,478
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 ...
Bangye's user avatar
  • 864
8 votes
0 answers
729 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 ...
Thatchaphol's user avatar
  • 1,130

1
2 3 4 5
10