Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,705
questions
3
votes
0answers
60 views
Problem in the paper “Stable Minimum Space Partitioning in Linear Time”
The paper Stable Minimum Space Partitioning in Linear Time describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in $O(n)$ time complexity ...
1
vote
0answers
70 views
Parametrization of context-sensitive language in polynomial time
Let $\Sigma$ be a finite alphabet. Let $L\subset \Sigma^*$ be a context-sensitive language containing a word of every length.
Can we always find $f:\Sigma^*\to L$ computable in polynomial time in ...
0
votes
1answer
53 views
Set cover where consecutive sets differ by at most one item [closed]
First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of ...
0
votes
1answer
51 views
How to build the tree with the “most different” solutions of a clustering?
Illustrate the question with an example : we have a similarity matrix for 1000 people, and the similarity represents how much their hobbies are the same (it does not really matter how it's built).
Let'...
2
votes
0answers
142 views
Theorem on non-decreasing probability of success of an algorithm
Question: What's a standard name/framework for the following, or some variant?
Stated briefly for a probabilistic algorithm: define $p_n$ as the conditional probability of success of a fork of the ...
9
votes
3answers
226 views
Sublinear Time Regular Expression Search
Does there exist a data structure with the following properties. Given a string $s$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows ...
1
vote
0answers
136 views
Triangle detection hardness in regular graphs
Consider a tripartite graph over $n^{1-\epsilon}$ vertices each in sets $I, J, K$. Suppose we impose a constraint that every vertex has degree $n^\epsilon/c$ for some constant $\epsilon > 0$ and ...
1
vote
2answers
164 views
Finding the point that maximizes a linear function
Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in ...
2
votes
1answer
119 views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
4
votes
0answers
79 views
Flipping one bit to maximize BMM output
Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative ...
1
vote
1answer
101 views
Finding output with unique witness in matrix multiplication
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication ...
3
votes
1answer
337 views
How hard is this combinatorial optimisation problem?
Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, ...
1
vote
1answer
145 views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.
Equivalently, $P$ is integral if ...
16
votes
4answers
3k views
Algorithms Careers
I’ve been writing software for a living for a number of years now. I have graduate background in mathematics and I am wondering whether knowledge of higher algorithms is utilized anywhere in industry. ...
5
votes
0answers
157 views
How to find the second smallest cut in a graph?
For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, ...
1
vote
0answers
47 views
Generalizing PageRank for tripartite graphs
Problem
I have the following directed tripartite graph $G(E\cup V\cup P, A)$, where there is a many-to-one symmetric relationship between the subsets V and E - $e\in E,v\in V,[e, v]\in A \iff [v, e]\...
0
votes
1answer
70 views
Given a partition and an element, find the subset that includes this element
I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
3
votes
1answer
81 views
Algorithm to find $n$ player nash equilibrium
This is the question asked 10 years before.
Most of the algorithm and software mentioned are out of date. I am wondering is there new approchs for this problem in the last 10 years?
The game dealing ...
2
votes
1answer
109 views
Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$)
I would like to check a sort of SMT formulas with two quantifiers where universal variables range over finite/bounded integer domains. An example formula is
$$\exists x \forall y ((y \ge 1 \land y \le ...
4
votes
1answer
300 views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.
...
5
votes
0answers
145 views
Minimum spanning tree, but with an unusual objective function
This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem.
If we have a rooted tree $T = (V,E)$ with root $r$, I first label ...
4
votes
2answers
162 views
The Dyck Language Correction Problem
Given a word $w$ over $\{ [, ] \}$, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make $w$ a Dyck word, i.e., a ...
3
votes
1answer
131 views
Fastest approximate triangle counting algorithms in dense graphs
One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the ...
2
votes
0answers
69 views
Is there an approximation algorithm for the three-person stable roommates problem? [closed]
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the threesome roommates problem, is NP-...
5
votes
0answers
164 views
Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover
This problem came up in my study of digraphs:
Given a connected bipartite graph $G = (A \cup B, E)$, a vertex cover is a set $S$ of vertices such that every edge has some endpoint in $S$.
Note that $A$...
12
votes
2answers
168 views
Is the exponent in the rectangular matrix multiplication convex?
My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a ...
4
votes
1answer
167 views
Is $GCT$ necessarily a negative result program?
$GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can ...
9
votes
1answer
189 views
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
10
votes
1answer
362 views
Is subtractive dithering the optimal algorithm for sending a real number using one bit?
Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
4
votes
2answers
199 views
Is there a linear time algorithm for integer multiplication verification?
There is a quadratic randomized algorithm for matrix product verification.
Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?
1
vote
1answer
74 views
Knapsack problem with dependent weight and profits among the items
I'm working on a problem that may be reduced to the following variant of multiple knapsack problem:
Each knapsack has its own valuation function; an item brings different profit and weight to a ...
3
votes
1answer
221 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}\...
13
votes
0answers
330 views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer [closed]
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
145 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 $\...
1
vote
1answer
109 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
146 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
118 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
44 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
38 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
273 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
98 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
317 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
60 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
43 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
174 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
141 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
118 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
65 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
37 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 ...
