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

learn more… | top users | synonyms (1)

2
votes
0answers
36 views

How to find a merge tree for a set of words?

Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider ...
3
votes
0answers
62 views

Is there a programming language where any arbitrary recursive function can be fused?

Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend ...
6
votes
0answers
71 views

Hierarchical sorting strategies for pattern-avoiding permutations?

For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := ...
5
votes
0answers
60 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 ...
0
votes
0answers
121 views

Most efficient algorithm to search an unsorted array with a very precise data structure

(I apologize in advance if this question sounds a bit practical, but I suspect it might have an interesting theoretical aspect.) I have a (large) array of data, not completely sorted, but with which ...
1
vote
0answers
40 views

What are some examples where the Catalan numbers show up in algorithms/data structures?

For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up ...
0
votes
0answers
40 views

What is the intuition behind Steiner point insertion rules?

I am reading a paper on Constrained Delaunay tetrahedralization (Meshing Piecewise linear complexes with Constrained Delaunay tetrahedralizations). It mentions rules for inserting steiner points but ...
25
votes
1answer
427 views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
8
votes
0answers
52 views

Minimum length cuts needed to remove holes in a polygon

Suppose I'm given a connected polygon in the plane with holes. I can "remove" a hole by drawing a straight line from the boundary of a hole to another boundary (either of another hole, or the boundary ...
3
votes
0answers
93 views

For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find $k$ disjoint paths between pairs of vertices $\{s_i,t_i\}_{i=1}^k$ in poly time for fixed ...
1
vote
2answers
199 views

For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist ...
14
votes
2answers
455 views

Comparing Two Algorithms for 3SUM problem over Integers

The paper "Subquadratic Algorithms for 3SUM", by Ilya Baran, Erik D. Demaine, Mihai Patrascu has the following complexity for the 3SUM problem: given a list $L$ of $n$ integers if there are $x,y,z ...
0
votes
1answer
46 views

Pairing algorithm for simple speed dating problem

I am asking myself whether there is an polynomial algorithm for the following problem: Given: ...
19
votes
3answers
932 views

Nontrivial algorithm for computing a sliding window median

I need to calculate the running median: Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$. Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, ...
3
votes
1answer
88 views

Polynomial-time distinguishability threshold of planted clique

I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution ...
7
votes
1answer
159 views

Algorithm to determine function equality on the simply typed lambda calculus?

We know that beta-equality of simply typed lambda-terms is decidable. Given M,N:σ→τ, is it decidable whether for all X:σ, MX $≃_β$ NX?
2
votes
2answers
80 views

Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density

Say I sample a set of points $(p_1,p_2,...) \in P$ from a probability distribution $f(x,y)$, e.g. a bivariate normal distribution, such that my sampling process chooses a point in the distribution ...
2
votes
1answer
107 views

Fast algorithm to distribute points evenly in a 2D grid

In an NxN grid, I want to select M points ($1 \leq M \leq N^2$) so that they are distributed as evenly as possible, spread out everywhere, edge to edge. Can you suggest a fast algorithm for ...
2
votes
2answers
125 views

Set packing with maximum coverage objective

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. Set-Packing asks how many disjoint sets we can pack, and is defined ...
2
votes
0answers
70 views

Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
4
votes
1answer
120 views

Is it possible to create an algorithm-aware optimizer?

I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm: ...
4
votes
1answer
132 views

Vertex disjoint simple paths of length k

A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths. Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there ...
7
votes
0answers
124 views

Is the following “Occam's razor” decision problem a member of P?

While thinking about natural language processing, I came up with the following NP problem: OCCAM-k: Given a fixed natural number $k$, consider the following input: a natural number of states $S$ in ...
9
votes
3answers
228 views

Does every greedy algorithm have matroid structure?

Its well established that for every matroid M and any weight function w, there exits a GREEDYBASIS(M,w) which returns a maximum weight basis of M. So, is vice-versa also true? That's if, there is some ...
3
votes
0answers
75 views

Multi-Agent Pathfinding

Quoting from Wang and Botea 2011: An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each ...
11
votes
2answers
535 views

How can I compute knots?

Is there a documented way to compute knots? (circumferences embedded in a 3-dimensional Euclidean space). I mean, a datatype to represent them, and an algorithm to determine if two instances of the ...
6
votes
0answers
66 views

Is there any known result for 1-median problem with negative weights in Euclidean space?

Given a set of $n$ points $v_1,\ldots,v_n$ in $R^d$, find a point $p$ such that $\sum_{i=1}^n w_i d(p,v_i)$ is minimized, where $w_i$ is the weight of $v_i$, which may be positive or negative. ...
10
votes
2answers
361 views

Sorting using read-only stacks

Consider the following setting: we are given a stack $s$ which contains $n$ items. we can use a constant $O(1)$ number of extra stacks. we can apply the following operations on these stacks: check ...
9
votes
0answers
101 views

Hardness of optimal sorting

For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known. From a purely theoretical perspective, however, exactly optimal ...
13
votes
1answer
230 views

Is DAG subset sum approximable?

We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$. The DAG subset sum problem (might exist under a ...
20
votes
15answers
4k views

Hard-looking algorithmic problems made easy by theorems

I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only. (2) ...
13
votes
4answers
407 views

Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs. I've seen the question regarding the other way around here “Directed” ...
2
votes
0answers
174 views

Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?

Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H_n$ greedy algorithm does not readily extend to the set partial cover problem, where the goal is to ...
1
vote
1answer
103 views

FPRAS for Perfect Matching

If you have FPRASes for counting number of matchings of size $\leq n$ and size $\leq n-1$, can you get an FPRAS for counting number of matchings of size $n$ (i.e perfect matchings)?
5
votes
0answers
100 views

Lower bound for the maximal vectors problem

I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, ...
3
votes
0answers
101 views

Building a “balanced” universal set

A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called $(n,k)$-universal if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, ...
7
votes
1answer
117 views

Linear-time algorithm for getting ends of diametral paths in special sequence of trees

Recently in my research I have faced with the following subproblem: Given a tree $T, |V(T)| = n$ and its vertices are ordered $v_1, \ldots, v_n$ so that $T_i = T_{i-1} - v_i, 1 \le i \le n$ and ...
5
votes
0answers
110 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 ...
3
votes
2answers
132 views

What is a precise definition of “in-place”?

"In-place" is a seemingly informal adjective used to describe algorithms. Does it have a precise definition? To further clarify the discussion, what models of computation can we say are in-place? We ...
1
vote
2answers
67 views

Path replanning in path finding algorithms

I'm working on a path finding algorithm for my thesis and I've gotten to a problem I need to solve where agents can replan their path if they need/have to. For example, if an agent is traversing ...
0
votes
0answers
18 views

Analyze tags similar tags

I have a system for tagging articles. Each editor ads different tags to each piece of content. For example: for A: George Washington, first president for B: first president, Washington George for C: ...
4
votes
0answers
72 views

Constructing a small (n,k)-Covering Matrices family

Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$. We call ${\cal A}$ a (n,k)-covering, if for every subset of columns $I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in ...
11
votes
1answer
212 views

Equivalence of feasibility checking and optimization for linear systems

One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the ...
6
votes
1answer
216 views

Constructing a k-perfect permutations family

I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, ...
1
vote
4answers
185 views

Efficiently generate list of lightest intervals of a vector

Suppose a vector of size $n$ is given. The goal is to compute, $\forall i \in [n]$ the lightest interval of size $i$ (i.e. the interval whose sum is minimal). For example, if we have the array: ...
-3
votes
1answer
132 views

Isn't weakly universal hashing even a stronger than truly random? [closed]

So as far as I know the weakly universal hashing is defined as: for any $x, y \subset U, Pr(h(x) = h(y)) \le \frac{1}{m}$ where m is a smaller number than the cardinality of $U$, and h are chosen ...
3
votes
0answers
310 views

What's the hardest problem with a non-trivial exact algorithm?

Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough. I’ve also came across some algorithms which are not practical even for very small inputs, and their ...
0
votes
0answers
61 views

polynomial time algorithm for integer programming with bounded dimension

Can anyone tell me the poly-time algorithm for integer programing with bounded dimension? I am not able to find the exact Lenstra's algorithm in a clearcut manner which elucidates the algorithm ...
1
vote
0answers
362 views

How to find interesting algorithms to implement?

I am not a researcher in algorithms (I am a college freshman). I would like to implement an interesting recent algorithm from a data structure/algorithms paper. How can find a good algorithms paper ...
4
votes
3answers
128 views

M-clique covers in complete graphs

Let us consider a complete weighted graph, with $NM$ nodes. Our objective is to find, among all possible combinations of $N$ disjoint $M$-cliques (each clique consisting of $M$ nodes), the ...