Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,665
questions
0
votes
0answers
15 views
Remove cycles from a stochastic comparison matrix, while doing the least amount of editing
Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
-3
votes
0answers
73 views
Is this case possible for the P/NP problem? [closed]
I was wondering if the following could be a possibility in the resolution of the P=NP problem.
Could it be that every algorithm(except one) for any NP complete problem is exponential in the general ...
-4
votes
0answers
34 views
Time complexity of counting the non-prime numbers
So i have a code that i need to find (and proof) the time complexity of it:
For ( i = 2 -> N )
For ( j = 2-> sqrt(i))
If(i%j==0)
K++
Break;
Would really appreciate if someone can help.
2
votes
0answers
82 views
Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?
Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the ...
19
votes
1answer
1k views
Has parameterized complexity led to better algorithms?
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
-1
votes
0answers
34 views
Is this some variant of online knapsack problem?
We have a set of $n$ bins with capacities $c_1, c_2, \cdots, c_n$. Now, I have items arriving in one by one with arbitrary sizes. I want to place the item in the bins in the following manner:
The ...
4
votes
0answers
76 views
Complexity of Encoding a Matroid Flow Problem in a Matrix
Context:
Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$.
We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
18
votes
0answers
356 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 ...
0
votes
1answer
46 views
Algorithm to calculate coordinated radio frequencies
I'm stuck on this algorithm problem for a project I'm working on. I can find no relevant documentation, and would very much appreciate any help that can be offered on this! I will try to explain it ...
0
votes
0answers
97 views
Algorithms and approximations for optimal offline binary tree operations
Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted ...
5
votes
1answer
77 views
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
4
votes
0answers
292 views
Deciding whether $2^k+m$ is prime
I thought something fancy can be done with number-theory or memoization, but neither worked for me. Being limited in knowledge I decided to ask experts.
Does there exist a deterministic polynomial-...
1
vote
0answers
44 views
Reference request: algorithm meta-analyses
Could you direct me to papers that survey families of algorithms? The ideal paper would focus on a single family of algorithms, would show how the improvements in each algorithm work, and ideally ...
3
votes
1answer
175 views
How can I optimize my brute-force solution to this problem?
I am working on a solution to the problem explained below. I am using brute force, I have reached the point where solutions are prohibitive, so I need to optimize more (if possible).
Of course, it ...
3
votes
1answer
122 views
Maximum subarray problem with weights
The maximum sum subarray problem involves finding a contiguous subarray with the largest sum, within a given one-dimensional array $A[1...n]$ of numbers. Formally, the task is to find indices i and j ...
3
votes
1answer
126 views
Polynomial evaluation at all different points
I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want
to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all ...
3
votes
0answers
93 views
On solving Planar Circuit SAT
This enquiry is three-sided.
Side 1 - State of the art
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$?
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
5
votes
1answer
169 views
Complexity of finding the most likely edge
Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.
Now consider the following random process. First sample a uniformly random ...
2
votes
0answers
49 views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following:
INPUT: a simple undirected graph $G$.
OUTPUT:
YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
2
votes
0answers
94 views
What's the constant coefficient of the Coppersmith-Winograd algorithm?
Every source I can find just says "too big to be practical."
3
votes
2answers
150 views
Match a string agains a set of regexes
There are several algorithms to match a (simple) string against a regular expression (see here).
But if we have a lot of regexes, can we find one of them that matches the given string faster than ...
3
votes
2answers
149 views
Complexity of Set Difference
Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes $...
6
votes
2answers
443 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 “...
6
votes
2answers
278 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
147 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
100 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 ...
2
votes
0answers
65 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
182 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
1answer
96 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
60 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
88 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
309 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
74 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
24 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
51 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
113 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
266 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
84 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
133 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
30 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
68 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
47 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
99 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
126 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
463 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
268 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
142 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 ...
