Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,680
questions
-4
votes
0answers
100 views
2
votes
0answers
91 views
An optimization problem
I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$
maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\...
14
votes
0answers
306 views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
4
votes
1answer
131 views
Minimizing $L_2$ norm of a vector with two distinct entries
Let $d\in\mathbb N$ and denote $V=\bigcup_{a,b\in\mathbb R}\{a,b\}^d$, the set of all vectors with two distinct values.
Given a vector $x\in \mathbb R^d$, I want to compute some $v^*\in V$ such that $\...
2
votes
1answer
96 views
Complexity of a satisfiability problem
I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below.
Given $n$ ...
2
votes
1answer
133 views
Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs
Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ...
0
votes
0answers
115 views
Triangle counting using approximate matrix multiplication — suspicious paper
This paper [1] claims that for matrices with entries in $O(1)$, one can approximately multiply them in time $O(n^2 \log 1/\delta)$ to within error delta in the Frobenius norm (Theorem 1 in that paper)....
3
votes
0answers
43 views
Counting subsets of bipartite graph part which admit an induced perfect matching
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect ...
0
votes
0answers
37 views
Maximum resistor with sublinear number of measurements
Consider a set $X = \{x_1, \dots, x_n\}$ of positive real numbers (or natural numbers, if you like) to be a set of resistors. For any subset $S \subset X$, we can build resistive circuits and measure ...
8
votes
1answer
259 views
Time complexity for a variant of edit distance
This question is about the following variant of edit distance. Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter ...
2
votes
0answers
94 views
$k$-XOR collision free families
Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies:
$\forall i: v_i\in\{0,1\}^{z_{n,k}}$.
The bitwise xor ...
8
votes
1answer
298 views
On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$
It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses.
Being $s_k=\...
2
votes
0answers
57 views
Can we always find a graph with a given algebraic connectivity?
This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong.
I would like to experiment with various spectral properties of graphs, ...
1
vote
0answers
38 views
Dynamic permutation cycle data
Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?
sameCycle($\pi,x,y$): determines ...
1
vote
1answer
99 views
An extension to the student/college admissions Gale-Shapley algorithm
The Gale-Shapley algorithm is an established algorithm that finds an optimal one-to-one match between two groups, each individual of which has a preference for the individuals in the other group (the &...
6
votes
0answers
130 views
Computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$
This question is about computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$.
The computation model we are considering is the unit-cost RAM machine with linear ...
2
votes
0answers
117 views
Finding nodes with enough unique ancestors
Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, \dots, v_n$. We ...
1
vote
1answer
60 views
Separating DAGs using separators consisting of lists of nodes and all ancestors
Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....
1
vote
0answers
36 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 ...
2
votes
0answers
84 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 ...
18
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, ...
4
votes
0answers
79 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
393 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
57 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
109 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
303 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
45 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
201 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
126 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
127 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 ...
4
votes
0answers
105 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
172 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
50 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 ...
5
votes
0answers
108 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
157 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
152 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
452 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
287 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
149 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
113 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
67 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
187 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
100 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
64 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
89 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
314 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
91 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
27 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 ...
