Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,857 questions
0
votes
0
answers
49
views
Testing if the intersection of affine flats and hamming ball is empty
Suppose as input we are given $W = a + V \subset \mathbb{F}_q^n$ where $V$ is a $k$ dimensional vector space. We are specifically given the basis of $V$ and $a$. Moreover we are given $y \in \mathbb{F}...
- 143
4
votes
5
answers
2k
views
Are there any examples of exponential algorithms that use a polynomial-time algorithm for a special case as a subroutine (exponentially many times)?
There are many examples of exponential algorithms that use polynomial algorithms for special cases as subroutines. Still, I was hoping to see one that uses a well-known polynomial algorithm for a ...
- 245
2
votes
0
answers
70
views
Terminology for computation vs. output
Is there a widely accepted name and/or notation for the computational process of an algorithm as opposed to its output? To clarify, suppose I have an algorithm $A$, and I denote as $A(x)$ the output ...
0
votes
0
answers
60
views
Binary Search with Probabilistic Comparison Errors
In a standard binary search on a sorted array, when you compare the item being searched ($x$) with the pivot ($m$), if $x < m$, then you recurse in the first half of the array; if $x > m$, then ...
- 101
0
votes
0
answers
16
views
Find all partitions at a given edit distance from a reference partition of n items
Suppose we have a given partition of n items, say P, and consider the "edit distance" from this question: Edit distance between two partitions.
How can we efficiently find all partitions (of ...
- 1
4
votes
0
answers
141
views
What's the state-of-the-art in generic unification?
The Wikipedia page on unification mentions several generalizations of the basic Robinson unification problem. These seem to boil down to
Making the terms in the domain of discourse more interesting (...
- 141
2
votes
0
answers
107
views
Are the algorithms developed for the 'gas station problem' and some seemingly derivative problems equivalent?
I have recently been examining the following recently published papers related to the 'Gas Station Problem,' a generalization of the shortest path problem that accounts for fuel consumption by the ...
- 21
2
votes
0
answers
71
views
Complexity of single bit recovery version of Integer Factorization problem
Consider the integer factoring problem with exactly 2 prime factors $p.q=N$. Given $N$ find the prime factors $p$ and $q$. The problem is notoriously difficult (on classical computers) and is the ...
- 851
2
votes
0
answers
143
views
Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks
Context
I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the ...
- 21
4
votes
1
answer
138
views
Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?
I'd like to know if the following generalization of min-cost perfect matching is NP-hard.
As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}_{\geq 0}$. In addition, ...
- 649
0
votes
0
answers
63
views
What is the proper name for a tree whose edges hold more than one symbols?
To supplement the title, edges from one node may hold strings with the same prefix.
For example, a node may have two edges, apple1 and ...
- 113
0
votes
0
answers
51
views
Can an m * n matrix be given Young Tableau property in O(1) space?
If it can be done with heaps why not Young Tableaux? [1]
I know that the analogy is too simplistic but for learning sake, let us consider it.
The only limitation I noticed is that while heaps exhibit ...
0
votes
1
answer
137
views
Time complexity of square root floor
Given a square number in $n$ bits can we compute its square root in $O(n)$ time?
In general can we compute $\lfloor\sqrt{a}\rfloor$ in $O(\log a)$ time?
- 13.3k
4
votes
2
answers
148
views
Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?
It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by ...
- 41
7
votes
1
answer
271
views
Is parity of GI easy?
Given graphs $G,H$ let $N(G,H)$ be the number of isomorphisms between them. Is there polynomial time algorithm to compute $N(G,H)\bmod 2^t$ for every fixed $t\geq1$?
- 13.3k
3
votes
1
answer
68
views
Quickest known integer relation algorithm in the case of signs
Let $x_1,\cdots,x_n,k$ be integers such that $|k|\le\sum_{i=1}^n|x_i|$.
What is the quickest known algorithm to determine $w_i\in\{-1,0,1\}$ such that $k=\sum_{i=1}^nw_ix_i$ where they exist?
What is ...
- 131
1
vote
0
answers
125
views
Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments
Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
- 21.1k
1
vote
0
answers
72
views
Closed-form for exact number of iterations of binary search
(This is a cross-post from CS.SE).
Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \...
- 111
1
vote
0
answers
168
views
Is finding the best permutation an NP-Complete problem?
We have a matrix $M$ of size $n$ by $n$ where
$M[i][j] \ge 0$ and $M[i][i] = 0$.
We want to create a permutation of integers $[1,\dots,N]$, like $\langle P_1, P_2,\dots,P_n \rangle$, such that
$$
\...
- 554
3
votes
0
answers
124
views
Why Huffman codes cannot be handled using matroid theory?
In Cormen's "Introduction to algorithms" it is stated that matroid theory cannot be applied to justify the greedy algorithm given for the construction of Huffman's codes. I was wondering ...
- 1,071
0
votes
0
answers
83
views
Evidence extended GCD is in $TC^0$
Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
- 13.3k
1
vote
1
answer
138
views
Bellman-Ford with infinite weights
I have a graph with weights of the form $a \omega + b$ where $a,b \in \mathbb{Q}$ and $ \omega$ is an infinite value, that is, a value such that for any rational number $q$, $q \le \omega$. The ...
- 1,071
1
vote
1
answer
154
views
How to Classify Memory Access Pattern by LLVM or Other Tools?
I am currently encountering issues with using LLVM. Here is my specific problem:
I want to study the memory access patterns of applications that are suitable for mapping onto a Spatial Accelerator, ...
- 11
4
votes
1
answer
86
views
Reference request: finite field computation over the Word-RAM model
Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$.
Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
- 696
7
votes
0
answers
82
views
Tree of addition chains
Addition chains are a well-known way of building up a number from 1 by adding two previously computed numbers. It is a long-standing open problem to determine the complexity of computing the length of ...
- 14.2k
1
vote
0
answers
72
views
Perceptual similarity problem in theoretical computer science
A perceptual hash is a type of locality-sensitive hash, which is analogous if the features of the images are similar. Let $I$ denote the set of images and $y_1 \approx y_2 $ means images are similar (...
- 123
3
votes
1
answer
125
views
How well can shortest common supersequence over small alphabet size be approximated?
Given a list $L$ of sequences of the first $n+1$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $L$? The paper here shows that if $n$ is not ...
- 228
0
votes
1
answer
97
views
Polynomial time algorihtms for two variants of the decision version of longest walk problem
I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm.
As I understand it, the longest path problem doesn't allow repetition of edges....
- 1,071
0
votes
0
answers
73
views
Shortest sequence that contains a given list of sequences as subsequences
Given an alphabet with $n$ characters, and a list $L$ of sequences can we approximately find the shortest sequence that contains all sequences of $L$ as subsequences?
Very similar to the question ...
- 228
1
vote
1
answer
67
views
Shorter than target vector path algorithm
Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
- 1,071
2
votes
1
answer
419
views
A question on combinatorial algorithm
Given n sets $S_1,...,S_n$ such that $S_i \subset \{1,...,n\}$ is there a poly(n) algorithm to find $1 \leq i_1 < i_2 <.... < i_k \leq n$ such that $|\bigcup_{j=1}^k S_{i_j} | = k$ where $1 \...
- 143
1
vote
0
answers
51
views
Constructing a DFA with $n$ states for which $L*$ needs $n$ equivalence queries
I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
0
votes
0
answers
23
views
Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets
I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
4
votes
0
answers
69
views
Is greedy minimax permutation rejecting sorting optimal?
I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$.
Initialize a list of all $n!$ permutations of size $n$.
For each possible pair of indices $i, j$, count how ...
- 895
0
votes
1
answer
60
views
Question about claw-free graphs
Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ?
There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
- 103
2
votes
0
answers
82
views
References for algorithms to compute approximating polytopes for arbitrary convex sets
There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes.
One of the main results in this area is that under some mild ...
4
votes
0
answers
90
views
Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?
Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
- 41
0
votes
2
answers
229
views
Shortest path with permutations and fixed dimension
I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on $...
- 1,071
0
votes
0
answers
97
views
What algorithms are there for ANN?
I'm a software engineer working on a large project for which one of the subcomponents involves approximately solving the nearest neighbors problem (to a factor of $1+\epsilon$). I was wondering what ...
- 11
5
votes
1
answer
138
views
Shortest path with affine updates and fixed dimension
One may look at the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with ...
- 1,071
1
vote
1
answer
91
views
Is there a conditional lower bound for the k max subarray sum problem?
Consider an array $A$ of integers of length $n$. The $k$-max subarray sum asks us to find up to $k$ (contiguous) non-overlapping subarrays of $A$ with maximum sum. If $A$ is all negative then this ...
- 3,912
10
votes
2
answers
383
views
Algorithm to check whether a given set is Sidon
We call a set of natural numbers $\mathcal S$ to be a Sidon Set if $a+b=c+d$ for $a,b,c,d\in \mathcal S$ implies $\{a,b\}=\{c,d\}$. In other words, all pairwise sums are distinct.
What algorithms do ...
- 203
3
votes
1
answer
144
views
Rearrange vectors so partial sums are all non-negative
Consider we are given a collection of $n$ vectors in $d$ dimensions, we want to decide if they can be rearranged into $v_1,\ldots,v_n$ such that $\sum_{i=1}^j v_i\geq \textbf{0}$ for all $j\in [n]$. ...
- 4,529
3
votes
1
answer
87
views
What is the fastest algorithm for computing exact network reliability?
In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
- 696
2
votes
1
answer
124
views
Maximum cardinality disjoint cycle cover in undirected graphs
I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
- 848
4
votes
1
answer
188
views
Is there a lower bound for the problem of finding the best straight line partition
I recently asked the following algorithms question on another site. The best answer so far is $O(n^4)$ time. The input is of size $O(n^2)$ and the output is just a number so I was wondering if there ...
- 3,912
0
votes
1
answer
258
views
Complexity of simplex method
What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints
- 1
4
votes
0
answers
109
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$$...
- 2,262
10
votes
0
answers
167
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 ...
- 2,023
58
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 ...