Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
466
questions with no upvoted or accepted answers
6
votes
0
answers
195
views
Complexity of Roman numeral evaluation
I came up with a result the other day that arbitrary length Roman numeral evaluation can be modeled as a monoid:
https://gist.github.com/4542999
1) Is this a known result?
2) If not, any ...
- 2,359
6
votes
0
answers
293
views
k-uniform k-partite hypergraph matching in polynomial time
I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers users here may provide. Please note that I have also asked this question ...
- 779
6
votes
0
answers
472
views
Cheapest dissection of a grid polygon into rectangles with cost
My problem:
Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.)
The rectangles must be taken from a predefined set (which ...
6
votes
0
answers
275
views
Tree rotation, a problem similar to Huffman coding
I am not sure whether the following problem has been studied.
We have a undirected tree $T$.
We would like to construct another tree $T'$.
$T'$ is a binary tree. Each inner nodes of $T'$ ...
- 769
6
votes
0
answers
343
views
Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?
Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate ...
- 1,327
6
votes
0
answers
105
views
Evaluate polynomial involving nearly-minimal graph cuts
So you want to evaluate the polynomial
$$
p(x) = \sum_{C} x^{|C|}
$$
where $C$ ranges over all nearly-minimum cuts in a graph (say, all minimal cuts of size $\alpha c$ where $c$ is the edge ...
- 3,488
6
votes
0
answers
354
views
Approximating the diameter of a convex set defined by semidefinite constraints
A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations.
Now, if you want to minimize a linear ...
6
votes
0
answers
293
views
Find the maximum set whose subset sum is unique for every of its subset
We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of these $n$ numbers such that
for any $T_1,T_2\subseteq S$, ...
- 769
6
votes
0
answers
221
views
Lowerbounds for in-situ permutation
What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth (...
- 161
6
votes
0
answers
247
views
Restricted Reachability Problem
Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
- 800
6
votes
0
answers
124
views
Fair and "robust" fallback permutations
The following is a fun problem we stumbled into today.
We have work we wish to distribute on machines $1..n$. Each piece of work is given a list of machines to try, in order. If any machine fails, ...
- 1,379
6
votes
0
answers
279
views
Huffman "terminator" bitstring
Motivation
Imagine a huffman compressed file that gets downloaded partially, like in P2P software, so we allocate disk space for the whole file first and then start downloading random file chunks. ...
- 161
6
votes
0
answers
268
views
Is there a algorithm for Max Cut on a Planar Directed Graph (MAX DIRECTED CUT ALGORITHM)?
Max Cut on a Undirected Graph has many algorithms when the Undirected Graph is Planar.
I have been wondering though if one could generalise this to Directed Planar Graphs?
- 1,578
6
votes
0
answers
151
views
Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range
I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this ...
- 299
6
votes
1
answer
722
views
Can this randomized greedy algorithm be made online? Or being proved impossible?
I am going to edge color an undirected simple graph. The following randomized offline algorithm is showed at Online Algorithms for Edge Coloring.
Offline: The potential colors are ordered 1, 2, . . ....
- 1,443
5
votes
0
answers
99
views
Fine-Grained Hardness for Undirected Hamiltonicity
The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time.
However, for undirected graphs on $n$ nodes, there is an ...
- 576
5
votes
0
answers
475
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$, ...
5
votes
0
answers
183
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 ...
- 607
5
votes
0
answers
189
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$...
- 607
5
votes
0
answers
92
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}\...
- 51
5
votes
0
answers
146
views
Interpolation of the square of a polynomial
Let $\mathcal{P}^2_n$ be the set of rational polynomials of degree at most $2n$ that are sqares of polynomials, i.e. $\mathcal{P}^2_n$ consists of the set of polynomials of the following form:
$$(a_0 +...
5
votes
0
answers
218
views
Is there a fast algorithm for inverting a sparse matrix?
I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working ...
- 235
5
votes
0
answers
281
views
What exactly did Lenstra prove on mixed integer linear program?
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
- 12.8k
5
votes
0
answers
226
views
Why is HyperLogLog (near-)optimal?
The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads:
Clearly, maintaining $\epsilon$-approximate counts till ...
- 329
5
votes
0
answers
211
views
On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input.
Is ...
- 12.8k
5
votes
0
answers
151
views
Online triangle counting
Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs.
Given a graph $G$ and a collection $C$ of subsets of ...
- 891
5
votes
0
answers
111
views
Algebraic dependence of roots of irreducibles over a finite field
I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math....
- 383
5
votes
0
answers
132
views
Vertex Disjoint Path Covers of Hypercube-Like Graphs
This is a followup question relating to an older question I posted, namely: https://cs.stackexchange.com/questions/55213/decomposing-the-n-cube-into-vertex-disjoint-paths.
Given a graph $G = (V, E)$ ...
- 101
5
votes
0
answers
247
views
Maximizing the number of selected edges with opposing requirements
Consider the following problem:
Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$.
Output: a subset of vertices $W$ of size $k$ which maximizes the ...
5
votes
0
answers
123
views
LPs with "sparse solutions"
Consider a graph optimization on a graph with n vertices and m edges that can be written as an LP (like say bipartite matching). By the duality with vertex cover, we know that there's a sparse dual ...
- 32k
5
votes
0
answers
198
views
Applications of Combinatorial Games in Computational Biology
I'm looking for general references in the literature about applications of games algorithmics in computational biology.
Q1. What are the notable cases of computational-biology or bioinformatics ...
- 650
5
votes
0
answers
133
views
Implications of a deterministic polytime prime-finding algorithm
I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem:
Given $n$ in binary, output a prime $p > n$.
I'm both curious about specific ...
- 7,595
5
votes
0
answers
213
views
Rebalancing balanced binary search tree when decreasing all keys to the right of a path?
Given a balanced binary search tree, suppose I have an operation decrease-right-keys(k, s) that operates as follows: when I call this operation on a tree $T$, I decrease all keys by $s$ in the right ...
- 313
5
votes
0
answers
483
views
Tuning Parameters of Locality Sensitive Hashing
We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ ...
- 639
5
votes
0
answers
106
views
What is the smallest deterministic construction of an ordered perfect hashing family?
A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$.
...
- 9,438
5
votes
0
answers
349
views
Practical algorithm for testing whether an edge is Delaunay
I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$.
My assumed ...
- 151
5
votes
0
answers
98
views
Upper bound on Euler characteristic of downward closed family
(Definition: $\mathcal{F}$ is called downward closed if for any $A \in \mathcal{F}$
and $B \subseteq A$ it holds that $B \in \mathcal{F}.$)
Let $\mathcal{F}$ be a downward closed family of subsets of ...
- 143
5
votes
0
answers
154
views
Union of two matching to maximize the number of cycles
Given $G$, $C$ and $M$, where $G$ is a graph with maximum degree $3$, $C$ is a hamiltonian cycle of $G$, and $M$ is a matching of $G$.
Let $\mathcal{N}$ be the set of all matching of $C$ with size $|...
- 4,367
5
votes
0
answers
202
views
Exploring a DFA, with no feedback
Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to ...
- 11.7k
5
votes
0
answers
1k
views
Minimum Number of Adjacent Swaps to Sort Numbers on a 2D Grid
Assume that we have $N$ numbers (labeled from $1$ to $N$) that are placed on a 1D (linear) array. For example, for $N=5$:
If we want to sort these numbers with the minimum number of adjacent swaps (i....
5
votes
0
answers
1k
views
Fast algorithm for successively merging k-overlapping sets?
Consider the following algorithm for clustering sets: Begin with $n$ sets, $S_1, S_2, \ldots,S_n$, such that $$\sum_{i = 1}^n |S_i| = m \,,$$ and successively merge sets with at least $k$ elements in ...
- 747
5
votes
0
answers
277
views
Big O notation for "modulo a polynomial"
Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition:
$f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$?
...
- 51
5
votes
0
answers
127
views
Truncated convolution algorithm
Suppose I have $n+1$-dimensional vectors $a$ and $b$. For each $i = 0, \dots, n$, I also have integers $0 \leq j_0(i) \leq j_1(i) \leq i$. I want to compute the following variant of a convolution:
$$
...
- 3,488
5
votes
0
answers
179
views
Online Interval Coloring Problem
We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $...
- 1,591
5
votes
0
answers
302
views
Sublinear time algorithm for maximum degree node
Here is a quick algorithmic problem: given a graph $G=(V,E)$ such that for each two distinct nodes $u,v \in V$ there's exactly one directed edge between them, and a probability $p$, such that each ...
- 531
5
votes
0
answers
160
views
What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?
In the algebraic decision tree, the result is clear: Elmasry and Belal (Verification Of Minimum Redundancy Prefix Codes)'s lower bound shows that the worst case complexity of computing an optimal ...
- 2,733
5
votes
0
answers
246
views
On the optimal solution of the CKR formulation for MULTIWAY CUT
Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U_i$ be those vertices in $V-T$ which is ...
- 2,560
5
votes
0
answers
213
views
Minimum infeasible subgraph in assignment problem
Given a bipartite graph $G$ with node set $(X+Y)$. Each node $x \in X$ has to be assigned to 1 node $y \in Y$. Assignment is only possible if there is an edge between $x \in X$ and $y\in Y$. ...
- 51
5
votes
0
answers
127
views
Finding an index set so that row sums are positive
Assume $A$ is a $n$-dimensional matrix of real numbers. The diagonal entries are non-negative, and all other entries are non-positive. I would like to find a subset $I \subseteq \{1, 2, \ldots n\}$ of ...
- 181
5
votes
0
answers
106
views
Quantized Unbounded Flow
I am interested in the following flow problem, since it turns out to be equivalent to a more general problem.
INPUT: A graph where each edge $e$ has an integer multiplier $q_e$, and a lower bound $...
- 1,100