Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

394 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
657 views

Approximation results for 3-partition

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
6
votes
0answers
225 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'$ ...
6
votes
0answers
326 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 ...
6
votes
0answers
104 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 ...
6
votes
0answers
324 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
0answers
292 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$, ...
6
votes
0answers
208 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 (...
6
votes
0answers
241 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 ...
6
votes
0answers
119 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, ...
6
votes
0answers
266 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. ...
6
votes
0answers
256 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?
6
votes
0answers
149 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 ...
6
votes
1answer
607 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, . . ....
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}\...
5
votes
0answers
128 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
0answers
201 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 ...
5
votes
0answers
177 views

What's the fastest known algorithm for finding the diameter of a graph?

Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?
5
votes
0answers
216 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 ...
5
votes
0answers
202 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 ...
5
votes
0answers
131 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 ...
5
votes
0answers
109 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....
5
votes
0answers
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)$ ...
5
votes
0answers
243 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
0answers
104 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 ...
5
votes
0answers
861 views

Is there a linear-time algorithm for max flow on dags

What is the fastest known algorithm for max flow on dags? Can there be a linear-time algorithm running in time $O(|V|+|E|)$? Input: a weighted dag $G=(V,E,w)$ where $E$ is given as an edge list $E$ ...
5
votes
0answers
170 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 ...
5
votes
0answers
129 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 ...
5
votes
0answers
206 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 ...
5
votes
0answers
383 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$ ...
5
votes
0answers
105 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$. ...
5
votes
0answers
275 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 ...
5
votes
0answers
94 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 ...
5
votes
0answers
150 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 $|...
5
votes
0answers
194 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 ...
5
votes
0answers
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
0answers
988 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 ...
5
votes
0answers
263 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))$? ...
5
votes
0answers
125 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: $$ ...
5
votes
0answers
163 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 $...
5
votes
0answers
289 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 ...
5
votes
0answers
159 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 ...
5
votes
0answers
217 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 ...
5
votes
0answers
195 views

Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC. My question is, can we do better for planar graphs? It is ...
5
votes
0answers
208 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$. ...
5
votes
0answers
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 ...
5
votes
0answers
103 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 $...
4
votes
0answers
95 views

2-hop distributed coloring in the CONGEST model

Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$. A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
4
votes
0answers
196 views

Find a pair of nodes with maximum sum of distances in k given trees

For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
4
votes
0answers
957 views

Optimizing Maximum Weighted Matching (Edmonds Blossom)

Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation ...
4
votes
0answers
194 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 ...

1 2
3
4 5
8