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
1answer
31 views

Maximum amount of appointments to schedule

Consider the following problem: There is a list of possible appointments for tomorrow, where each appointment is in the format [start time, end time]. Using this list, find the maximum number of ...
0
votes
0answers
24 views

how to efficiently compute mean function m(t) for non-homogeneous Poisson

Suppose that I know all intensity functions lambda(t) during given period [0,t], how can I compute the mean function m(t) for non-homogeneous Poisson process? Basically, m(t) in the integral of ...
5
votes
0answers
74 views

Time complexity of a branching-and-bound algorithm

Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
2
votes
2answers
198 views

Counting occurences of 'a' in a book faster than O(n)? [closed]

I was asked the following question in an interview: How would you count the occurrences of character a in a 500-page book? For simplicity, assume that you are ...
6
votes
0answers
87 views

Maximum weight “fair” matching

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching". Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
-2
votes
0answers
12 views

determing the max flow with only edge capacities from n/w with additional vertex capacities? [on hold]

Let ((V, E); s, t; c) be an extended flow network where not only edge capacities, but also vertex capacities are constrained, i. e., c : E ∪ V → R^ + 0 and a flow f : E → R^ + 0 must satisfy, in ...
-3
votes
0answers
34 views

FPTAS for bin packing [on hold]

If an algorithm for bin packing has a guarantee of OPT(I)+log^2(OPT(I)), then there is a fully polynomial approximation scheme for this problem. I have to prove this statement, but I have no idea ...
6
votes
4answers
220 views

Finding a permutation $p$ of $x_1, x_2, \dots, x_n$ which maximises $\sum_{i=1}^{n-1}|x_{p_{i+1}}-x_{p_i}|$

Here is the algorithmic problem I'm trying to solve: Given a list of integers $x_1, x_2, \dots, x_n$ find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximises the sum ...
5
votes
1answer
85 views

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why? Details: http://en.wikipedia.org/wiki/Powerset_construction states that the ...
-1
votes
0answers
63 views

max spanning tree with conditional weights

Consider the max spanning tree problem in which for any $e \in G$ there is a fixed $f(e)$. Suppose I have a graph with conditional values of the following form: $$ f(e) = \begin{cases} v_1 & ...
0
votes
1answer
105 views

checking isomorphism between K regular graph

Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that ...
10
votes
0answers
89 views

Is it possible to find the median with a linear size sorting network?

Is there a sorting network that makes only $O(n)$ comparisons and finds the median? The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of ...
13
votes
1answer
262 views

Computing parity of a permutation in a streaming-fashion way

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
2
votes
0answers
55 views

Recent insights on algorithms for 1D bin packing

This is just a general question on recent algorithms for the 1D bin packing problem. I just want to collect some information on this issue, so I’m grateful for any information. Especially heuristics ...
1
vote
2answers
74 views

Sketches, using ideal hash functions

I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.). They use hash functions that are required to be ...
6
votes
2answers
238 views

Streaming algorithms suitable for undergrad course

I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course. Good choices should probably satisfy the following requirements: ...
17
votes
1answer
129 views

Minimal cumulative set sum

Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$. Are there known algorithms ...
0
votes
2answers
132 views

Logic with Linear Programming

Can first-order logic be modeled/simulated as linear programming or integer programming? What about other forms of logic (say second order)? Update: am actually not a theory person, but more on the ...
6
votes
0answers
48 views

Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
0
votes
0answers
60 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 $$ ...
0
votes
0answers
45 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
85 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 ...
19
votes
0answers
503 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
140 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
87 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
92 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
113 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 ...
12
votes
2answers
356 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
151 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
291 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
35 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
289 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
65 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
74 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
123 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
75 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
186 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
193 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
467 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
81 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
194 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
91 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
177 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 ...
9
votes
1answer
234 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
471 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
183 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
401 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
78 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 ...