Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,646
questions
5
votes
2answers
203 views
Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis
In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
5
votes
2answers
137 views
3SUM Complexity—A special(?) Case
In the paper “Consequences of Faster Alignment of Sequences” by
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
1
vote
1answer
130 views
What is the complexity of this submatrix selection problem?
We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks.
We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum ...
0
votes
1answer
67 views
Minimizing the gaps with incremental capacity
There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 ...
-4
votes
0answers
30 views
Linear Time Sorting Using Density Towers
I was wondering if it was possible to write a linear-time sorting algorithm using a density tower. This is completely theoretical but essentially what I am thinking about is injecting masses into a ...
2
votes
0answers
63 views
Is there a fast algorithm for computing the Schmidt decomposition
I have a huge covariance matrix, 𝑀, with the dimension, e.g., $10^8 \times 10^8$. Luckily enough, the number of nonzero eigenpairs, $n$, is very small, i.e., $n<5$. From the computational ...
0
votes
0answers
180 views
Add edges to a DAG to maximize increase in number of connected vertices
Let $G$ be a Directed Acyclic Graph.
$$C(G) = \bigl|\{(u,v):u,v\in V(G),v \text{ reachable from } u\}\bigr|$$
Goal is to add $k$ edges in a DAG such that for the new $G'$, $C(G')$ is maximized.
...
-1
votes
0answers
33 views
Application of a Poisson inequality in the networks
I know that there are many works where Poisson (https://en.wikipedia.org/wiki/Poisson_distribution) processes are used in the construction of networks models. I am seeking for a model which can be ...
-1
votes
1answer
94 views
Required sample size to hit certain subset of a ground set
Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N_1,\cdots,N_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\...
0
votes
0answers
42 views
understanding generalized coupon collector for distributions or learning mixture of distribution
Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
2
votes
0answers
56 views
Complexity of computing Earth Mover's Distance when the costs satisfy the triangle inequality
Let p and q by two categorical probability distributions over $\{1,2,...,k\}$. Given a set of costs $c_{ij} \ge 0, i,j \in \{1,2,...,k\}$ that satisfy the triangle inequality, that is $c_{ij} \le c_{...
0
votes
0answers
80 views
NP-Hard or PTIME?
I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the ...
6
votes
2answers
302 views
On the complexity of a “list” datastructure in the RAM model
I am interested in the complexity of a data-structure equipped with the following operations (similar to a list):
insertion of an element at a given position within the list
deletion of an element at ...
3
votes
1answer
70 views
Interval partitioning with restrictions: NP-complete or efficiently solvable?
The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. ...
1
vote
0answers
22 views
Are the intermediary sets in maximum cardinality search optimal in some way?
The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...
-3
votes
1answer
50 views
Finding a non-negative solution to an integer system of linear equations
Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
3
votes
1answer
110 views
What is the complexity of this weighted b-edge matching problem?
I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:
Input: An undirected multigraph $G = (V, E)$ without
loops, an edge partition $(E_1,...
0
votes
1answer
194 views
Time complexity for multiplying two lower triangular matrices
I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
...
5
votes
0answers
80 views
Optimal point placement on integer lattice
What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute
\begin{eqnarray*}
\mu_1(N,n)\triangleq\min_{\mathcal{P}\...
7
votes
0answers
127 views
Subgraph isomorphism on graph sequences
I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences.
Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...
0
votes
0answers
28 views
Best known bounds on feedback arcset in high-girth directed graphs?
I asked this question over at MathOverflow, but thinking about it a little more I think it is a more natural fit here.
Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every ...
1
vote
1answer
66 views
Running an algorithm for fixed amount of time on RAM model machine
Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "...
0
votes
0answers
46 views
Can we multiply two numbers more efficiently (using binary circuits) if one of the numbers is fixed? [duplicate]
Let $a_1, a_2 \dots$ be a sequence of natural numbers, where $a_i$ has bit length $i$. Consider a function $f_n : \{0, 1\}^n \to \{0, 1\}^{2n}$ defined as $f_n(x) = a_n \cdot x$ ($\cdot$ is ...
1
vote
0answers
65 views
Combinatorial problems in electronics
This could be a downvoted question but I am asking because I am not able to get usable info via Google.
Are there any interesting combinatorial problems in the field of electronics circuits design? I ...
2
votes
1answer
96 views
Are string palindrome questions practically interesting?
I've been reading Don Gusfield's "Algorithms on Strings, Trees, and Sequences", and quite a some chunk of the textbook concentrates on palindromic-related ideas.
I'm unsure as to whether this is ...
9
votes
0answers
123 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 ...
0
votes
0answers
16 views
Why is it more efficient to merge larger runs higher in the tree than perform a balanced tree of merges in an unbalanced ping-pong merge?
While studying the research paper published by Microsoft in 2014, I stumbled upon Unbalanced Ping-Pong Merge.
In section 3.2 of the paper, it discusses about merging two sorted runs at a time. It ...
3
votes
3answers
438 views
Best parameterized algorithm for maximum clique
I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "...
2
votes
0answers
107 views
Time Complexity for Nearest Neighbor Searches in kd-trees
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of ...
3
votes
1answer
140 views
Convex polygons inclusion relation
I have the following problem which came as a subproblem in some work I was doing and I am completely stuck.
Note that I am interested in it only in terms of worst case time complexity (not heuristics ...
18
votes
3answers
593 views
Examples of the value of proofs for algorithms
In teaching Intro. Algorithms to undergrads, one of the most difficult tasks is to motivate why they need to know how to prove things about algorithms. (For many students, at least in many US ...
3
votes
0answers
88 views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
14
votes
2answers
1k views
NP-hard problems with very fast exponential-time algorithms
NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare.
Is any fact like
"For any constant $\epsilon>0$ there is an NP-hard 'natural' ...
3
votes
0answers
116 views
Matrix multiplication when one matrix is fixed
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry
One is allowed to pre-process this matrix as appropriate.
Given another positive integer entried $B$...
1
vote
1answer
281 views
Potentially stronger form of non-$ETH$
If we have a $2^{n^a}$ algorithm to $K$-$SAT$ where $a<1$ for all $K>2$ then $ETH$ fails and literature gives consequences. What are the consequences if $a=o(1)$?
9
votes
0answers
136 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 ...
5
votes
1answer
234 views
What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?
What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?
What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates ...
0
votes
1answer
99 views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
2
votes
0answers
100 views
Can you partially sort using $O(\log n)$ comparisons per element?
Input is a list of $n$ integers in an array A. Desired output is stored in Array B, such that $|rank(B[i])- i | \leq \sqrt{n}$.
Can this be done using $O(\log n)$ comparisons per element?
Just looking ...
2
votes
1answer
74 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 ...
0
votes
0answers
64 views
Generalization of k-Coloring: maximizing the number of vertices with no neighbours of same color
One can consider the following generalization of the $k$-Coloring problem:
Let be given a graph $G$ and an two integers $k$ and $p$. A vertex $v$ of $G$ is properly colored if $v$ has no neighbour ...
6
votes
1answer
230 views
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.
There is also a parameterized algorithm for ...
5
votes
1answer
134 views
Consequences/existence of problems without any “optimal” algorithm
Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off ...
0
votes
2answers
442 views
Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums
My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's ...
-2
votes
1answer
118 views
An efficient algorithm for maximizing gain by choosing from a set of options
(I hope this is on-topic for this site -- mods feel free to send this to another stack exchange if not )
I've got an optimization problem where I need to choose from one of several options to ...
-1
votes
2answers
126 views
Hospital Resident Matching Algorithm with Incomplete Preferences
Consider a set of doctors $D$ and hospitals $H$ such that each doctor $d \in D$ has a rank ordered strict preference over a subset of hospitals, $H_d \subseteq H$. Similarly, each hospital $h \in H$ ...
2
votes
0answers
78 views
Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree
I have encountered an interesting problem that I couldn't find any references to solve:
Determine the smallest subset of nodes that
need to be removed from an undirected graph to make it a tree.
...
2
votes
0answers
69 views
Cost of in-place partitioning integer arrays
Suppose we are given an array $a\colon[n]\to[m]$ of length $n$ (and each entry is between 1 and m). We will denote the $i$th entry of the array as $a[i]$.
Task: Permute the array $a$ in-place so that ...
4
votes
1answer
146 views
Given a subset of of the hypercube and an affine transform of it, find the affine map
This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some ...
7
votes
0answers
173 views
Tortoise and hare algorithms
Consider the problem:
Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$.
This problem has a stunning solution running ...
