Questions tagged [ds.algorithms]

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

Filter by
Sorted by
Tagged with
4 votes
0 answers
91 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$$...
11 votes
1 answer
666 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 ...
10 votes
0 answers
142 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 ...
57 votes
10 answers
18k views

Recent advances in computer science since 2010?

Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example, Asymmetric numeral systems for compression (e.g. Ubuntu ships with ...
0 votes
1 answer
74 views

Exchange cards with sum requirement

Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
29 votes
4 answers
1k views

Compendium of the Best Approximation and Hardness Results for NP optimization problems

Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result? Based on the feedback, it seems that it is safe to assume there is not such a ...
2 votes
4 answers
6k views

Complexity of greedy coloring

I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale They describe the Greedy algorithm as follows: ...
1 vote
0 answers
38 views

Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights

I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
2 votes
0 answers
42 views

Effective algorithms for finite lattices of (higher-order) monotonous functions?

I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
6 votes
1 answer
384 views

Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$

Can it be done in linear or at least subquadratic time?
20 votes
10 answers
3k views

What are examples of recent relatively simple 'toolbox algorithms'?

Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc. There are also several relatively standard data structures, such ...
0 votes
0 answers
46 views

Deamortization of basic COLA (Cache oblivious lookahead array)

I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA. The paper says that for every level k, for deamortization, ...
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 ...
4 votes
1 answer
85 views

Independent set queries with preprocessing

Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
2 votes
0 answers
36 views

Generalization of Binary Decomposition to Polynomials?

Given an integer $x\in\mathbb{Z}$, we can write its binary decomposition (and more generally base $B$ for $B\in\mathbb{Z}$, $B>1$) as $$x = \sum_{i=0} x_i B^i,$$ where $x_i \in \mathbb{Z}/B\mathbb{...
2 votes
1 answer
168 views

Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?

The algorithms I know for solving 3SAT typically have exponential run-time distributions which become wider in their PDF as the number of variables, $N$, increases. For the exponential distribution ...
5 votes
1 answer
147 views

Finding $k \times k$ rectangle in a matrix with maximum sum

Given an $n \times n$ matrix $A$ with $0-1$ entries, I want to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I| = |J| = k.$ I expect the problem to be NP-hard, so I want a polynomial ...
6 votes
1 answer
342 views

Condition Number dependent algorithms for matrix operations

Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
-1 votes
1 answer
86 views

How is memory being used by an algorithm, to define its space complexity? [closed]

In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
0 votes
0 answers
58 views

kd-tree optimality for orthogonal range search

It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
1 vote
0 answers
45 views

Compute Fourier coefficients from Single Fourier coefficient and initial vector?

I have some vector $\vec v\in\mathbb{Z}_q^n$, and would like to obtain $n$ vectors $\vec f_0,\dots, \vec f_{n-1}$ where $\vec f_i = (\mathcal{F}(\vec v)_i,0,\dots,0)$, i.e. each vector is a single ...
2 votes
0 answers
102 views

Is there a calculus or formalism for measuring set relations between algorithm outputs?

I'm asking this question from a fairly naive position, so apologies in advance, etc. I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested ...
12 votes
1 answer
2k views

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
1 vote
1 answer
46 views

What is known about the complexity of Network Diversion?

In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
0 votes
0 answers
42 views

Speed networking algorithm

I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
1 vote
1 answer
47 views

Maximizing merges with restrictions

Note: The input to this problem has type List[List[List[Pair[int, int]]]]. Since it's tricky to visualize that, I'll use terminology from the original problem, which comes from the optimization of ...
-3 votes
1 answer
134 views

help me understand what semiprime factorizations are worth

Based on a response I received in another post, I would like to ask this question. Are there semiprimes that are not very interesting in terms of research and are not worth factoring? Are only the RSA ...
3 votes
0 answers
82 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, ...
1 vote
1 answer
78 views

Can fair ordering of transactions be achieved in permissionless blockchains?

Front running attacks mainly happen because adversaries are able to manipulate the order of the transactions on blockchains. As many research paper address the problem of fair ordering, I don't find ( ...
1 vote
1 answer
55 views

Processing times of different job types on $n$ processors

I have $n$ processors that each receive an infinite sequence of jobs that have different processing times. In the simplest case, $n = 2$ and jobs are either $\texttt{fast}$ or $\texttt{slow}$ with ...
8 votes
0 answers
171 views

Can one find good distance-2-separators in planar graphs?

It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph. However, it ...
0 votes
0 answers
87 views

Consequences of early-exiting BFS after reaching the target node in Dinic's algorithm

In a typical exposition (or implementation), Dinic's algorithm executes a full BFS traversal of the residual graph starting from the source node in each phase. If the target node is unreachable, the ...
5 votes
1 answer
147 views

Reconstruction of a sequence generated by a Markov chain - reference request

Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols ...
9 votes
2 answers
920 views

Is this a known combinatorial optimization/scheduling problem?

We are given $n$ stacks which hold "items" of different colour and a machine that can process multiple items of the same colour in one go. At each step, we can remove one item from the top of each ...
2 votes
1 answer
184 views

On parallel complexity of modular inverse

Modular inverse is not known to be in $NC$ either. How about the cases where the modulus is just $2^n +i$ where $i\in\{-1,0,1\}$? Are these cases in $NC$? Are there any non-trivial classes of moduli ...
1 vote
0 answers
42 views

What are the fastest known parameterized algorithms for Grid Tiling?

Let $k$ and $n$ denote positive integers. In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
9 votes
1 answer
475 views

Most efficient inplace merge algorithms (stable and unstable)

I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...
46 votes
8 answers
21k views

Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
-3 votes
2 answers
184 views

pq factorization

If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful? p=(2^1024-1)+644 prime factor q=(2^1028-1)+188 prime ...
10 votes
3 answers
2k views

Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
37 votes
5 answers
2k views

Integer multiplication when one integer is fixed

$n$ is a parameter in the problem. For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$. Problem: Given $n$ what is the complexity of ...
0 votes
0 answers
45 views

What Data Structure storing points in space for fast lookup of stored points "near" a query point?

In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
6 votes
1 answer
573 views

Find odd-ranked numbers from a list

From a list of $n$ distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need? I could sort the whole list using $O(n\log ...
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 ...
11 votes
1 answer
6k views

What is the fastest algorithm for calculating nth term of Fibonacci sequence?

If we exclude methods that include precalculating of all Fibonacci numbers up to a sufficiently large number of n what would be the fastest algorithm for calculating nth term of Fibonacci sequence? I ...
1 vote
0 answers
56 views

Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them

In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
0 votes
0 answers
47 views

Complexity of XOR-Knapsack

Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
0 votes
1 answer
197 views

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define $$ f_{\mathfrak S}(z) := \sum_{\...
3 votes
2 answers
160 views

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by \begin{eqnarray} \langle x,y\rangle_{\...
2 votes
0 answers
66 views

Confusion with the definition of Online Set Cover

I am confused on a technicality on how Online Set Cover is defined. One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...

1
2 3 4 5
37