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

learn more… | top users | synonyms (1)

0
votes
0answers
54 views

k closest points that belong to a set

This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind. I have a set of real vectors: $$ S = \lbrace v_1, \dots, v_n \rbrace $$ ...
-3
votes
0answers
38 views

Maximum flow problem with both minimum and maximum capacities [on hold]

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum ...
0
votes
0answers
38 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have n cannisters that must go into m trucks that can each carry k cannisters. You require that no truck becomes overloaded, and for each cannister, there is a ...
0
votes
1answer
80 views

Finding optimal subset for quadratic function

Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a set $S$ of ...
17
votes
0answers
402 views

Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

The following question arose as a side product of some work I have been part of recently. An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a ...
4
votes
1answer
134 views

Explaining computer science algorithms/concepts/ideas using metaphors

Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even ...
1
vote
1answer
83 views

Data structure that allows moving groups of elements into buckets

I'm looking for a data structure that can do the following geometric operation: Suppose there are a set of buckets $b_0, b_1..., b_n$ each of which contains some elements. Suppose I want to move all ...
3
votes
1answer
88 views

Locally sorted sequences

Let $S=s_1,\ldots,s_n$ be a sequence and $p$ be a permutation on the indices of $S$ such that $p$ sorts $S$. Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | ...
-3
votes
1answer
108 views

What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
1
vote
0answers
173 views

Reconstructing a string from random samples [closed]

What is known about the following problem? Reconstruct a string $\sigma$ of known length $n$ over a known alphabet $\Sigma$ from a collection of uniformly and independently chosen $k$-long ...
11
votes
0answers
195 views

What is this variant of set cover problem known as?

Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
8
votes
1answer
149 views

Efficient Reduction from Min Cut to st-Min Cut

I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut. But the question of efficient reduction from min cut to $st$-min cut is still interesting to ...
12
votes
1answer
286 views

Optimal randomized comparison sorting

So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to ...
2
votes
0answers
34 views

2-dimensional dynamic set retrieval

For the following, $(w,x) >= (y,z)$ iff $w >= y$ and $x >= z$. I have a list, $L$, of $k$ points with integer coordinates ranging from $0$ to $n-1$. Each point has an associated set. I ...
8
votes
0answers
284 views

Is it possible to solve perfect matching in linear time

As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft. Is it possible to solve perfect matching problem in linear time for given ...
0
votes
0answers
64 views

locality-aware Mergesort

Let $A$ be an array with a total order to be sorted. We say $A$ has locality $d$ iff each element is at most $d$ indices away from its final index in the sorted array. In the locality-aware mergesort, ...
5
votes
1answer
68 views

Is there an extension to the stable roommates problem with multiple roommates per room?

The stable roommates problem presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to ...
4
votes
0answers
120 views

Problems in dynamic algorithms in computational geometry

The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as: Dynamic ...
3
votes
0answers
74 views

Online bridge and nonbridge counting (identification)

I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of ...
3
votes
1answer
183 views

Can two strings be matched as disjoint subsequences of a string?

Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a ...
11
votes
1answer
181 views

Correctness proofs of classic Paxos and Fast Paxos

I am reading the "Fast Paxos" paper by Leslie Lamport and get stuck with the correctness proofs of both classic Paxos and Fast Paxos. For consistency, the value $v$ picked by the coordinator in phase ...
18
votes
1answer
464 views

Is P equal to the intersection of all superpolynomial time classes?

Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$. It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf ...
-3
votes
1answer
77 views

Iterated Prisoner's Dilemma Algorithms

While reading a post on Scott Aaronson's blog about Eigenmorality, I ran across the idea of the iterated prisoner's dilemma tournament. I've studied some TCS on my own, but had never really thought ...
5
votes
0answers
191 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$ ...
1
vote
1answer
89 views

Generalized Secretary Optimization Problem

In the standard Secretary Problem, the goal is to hire the best secretary from a list of candidates. I've recently witnessed a failed hiring attempt for a needed position and it inspired a similar ...
-1
votes
1answer
170 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...
8
votes
1answer
230 views

Secretary hiring game

This is an extension of the classical secretary problem. In the hiring game you have a set of candidates $\mathcal C=\{c_1,\ldots,c_N\}$, and order on how skilled each worker is. W.l.o.g, we assume ...
13
votes
1answer
460 views

The complexity of counting simple paths in a directed graph

Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$. I would expect the problem to be #${\mathsf ...
4
votes
0answers
182 views

Balanced Boolean function satisfiability

Consider the following problem: Input: A Boolean black-box $U$ of a balanced Boolean function (balanced meaning equal number of satisfying and unsatisfying truth assignments) Output: A ...
3
votes
3answers
395 views

Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs?

There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances. What is the fastest algorithm for HC problem on cubic planar graphs? Is there a ...
0
votes
0answers
73 views

Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
0
votes
0answers
137 views

Greater-Than operator using an Arithmetic Circuit

How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it? Where $x$ is the input to the ...
1
vote
1answer
125 views

Separated 3Sum versus 3Sum problem

Does it matter in the 3Sum problem if the numbers to be summed belong to the same set or to distinct sets? Let's define the problem "$k$-Sum" as follows: given a single finite set of integers ...
9
votes
1answer
279 views

Finding similar vectors in subquadratic time

Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the similarity function. Examples of similarity function are cosine distance, $l_2$ norm, Hamming distance, Jaccard ...
10
votes
0answers
181 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
1
vote
0answers
106 views

Computing a sparse eigenvector

Given a matrix $A$ with distinct eigenvalues, can I find a sparsest eigenvector of it in polynomial time? It is tempting to say that one can simply compute the eigenvectors and pick the sparsest ...
1
vote
0answers
146 views

Dynamic Programming with two optimization goals

I am working on the problem of distributed database query planning. Existing work [1] uses dynamic programming to search the potential query plan space and find the one with minimal cost. However, I ...
-3
votes
1answer
83 views

Is this NP-Hard or does a known optimal polynomial time solution exist? [closed]

Suppose we have 10 items, each of a different cost Items: {1,2,3,4,5,6,7,8,9,10} Cost: {2,5,1,1,5,1,1,3,4,10} and 3 customers {A,B,C}. Each customer has a requirement for a ...
17
votes
1answer
586 views

Edit distance in sublinear space

What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input? I assume the input is ...
4
votes
4answers
759 views

Factoring as a decision problem

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
7
votes
0answers
89 views

Computing the most likely winner in elections : intermediate case between Kemeny and Borda?

Given $n$ possible alternatives satisfying some unknown linear ordering, a multiset of pairwise votes, i.e., a matrix $M\in\mathbb{N}^{n\times n}$: $M_{i,j}$ counts the number of votes for which ...
9
votes
0answers
122 views

Maximum local edge connectivity

For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
0
votes
0answers
92 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
3
votes
2answers
139 views

Most frequent $aXa$ substring

Let $s\in\Sigma^*$ be a string, for some alphabet $\Sigma$. We want to find the most frequent repeated substring $q$ of $s$ such that its first character equals its last one, i.e. the most frequent ...
1
vote
0answers
69 views

Is there an algorithm that, given a point cloud, infers an optimal wireframe (surface) structure?

I have a point cloud that I would like to convert to a surface, in the form of a wireframe lattice structure. This means, from a sequence of 3D points (x,y,z), obtaining three 2D matrices X,Y,Z of ...
3
votes
0answers
93 views

Algorithm (parallel and serial) for Gram-Schmidt

Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the ...
7
votes
3answers
922 views

Are there any cases where quantum has given insight for classical algorithms?

To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum ...
3
votes
1answer
172 views

Applications of Harrow's algorithm for solving linear equations

In Harrow's algorithm for solving a system of linear equations the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a ...
1
vote
0answers
103 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
5
votes
0answers
70 views

Perfect hashing family variation - injectivity on $r$ disjoint sets

We denote by $[t]$ the set $\{1,2,\ldots,t\}$. A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S ...