Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ds.algorithms]

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

2
votes
0answers
49 views

What is the competitive ratio of a $d$-way associative LRU cache?

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
20
votes
4answers
1k views

Positive topological ordering, take 3

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix? This question is motivated by this problem: Positive topological ordering ...
0
votes
0answers
53 views

Coordinate descent in integer programing: when does it work?

Denote $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to minimize a function $f:N\rightarrow \mathbb{R}$. It is very easy to minimize $f$ coordinate by coordinate so ...
5
votes
1answer
292 views

Solving “all-marginals” problem for independent sets on grid

Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\...
20
votes
1answer
2k views

Finding the distance between two polynomials (represented as trees)

A colleague who works on genetic programming asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy ...
-3
votes
0answers
50 views

Optimal algorithm to compare lines of different files without repetition [closed]

I have 1600 ASCII files with 1000 lines in each file. Each line has only one entry and is a floating point number e.g. 1.67923. Let's denote the line1 of file1 with ...
17
votes
3answers
429 views

Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
348
votes
93answers
108k views

Algorithms from the Book.

Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book. If ...
31
votes
5answers
918 views

what is easy for minor-excluded graphs?

Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded ...
4
votes
1answer
542 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 ...
0
votes
1answer
93 views

Permuting the columns of a 0/1-matrix to avoid short segments

Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
5
votes
0answers
99 views

Evaluating addition chains

I hope this is a suitable place to ask this question. An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
1
vote
0answers
30 views

PTAS for projective clustering : survey

$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below: Given a $j$-...
-4
votes
2answers
77 views

Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...
5
votes
1answer
64 views

Pop desired elements on stacks of bounded capacity

Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color. Only push and pop are allowed on ...
5
votes
1answer
188 views

Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always ...
9
votes
2answers
5k views

Time complexity of Held-Karp algorithm for TSP

When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, I came up with the following question: why the complexity of their algorithm for TSP ...
3
votes
1answer
197 views

Finding self-similar homomorphisms of a FSM transducer

Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function ...
2
votes
1answer
69 views

Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
2
votes
1answer
88 views
7
votes
1answer
3k views

What is the fastest algorithm for calculating nth term of Fibonacci sequence?

If we exclude methods that include precalculating of all Fibonacci numbers up to a sufficiently large number of n what would be the fastest algorithm for calculating nth term of Fibonacci sequence ? ...
3
votes
1answer
758 views

Minimal Cost of Eulerian Path

Problem: Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also ...
1
vote
0answers
112 views

How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
2
votes
1answer
96 views

Minimization version of matrix p-norms?

I considered a minimization version of matrix p-norms, defined for a matrix $A$ by $$ f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}. $$ Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
16
votes
1answer
1k views

Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
1
vote
1answer
149 views

How can I rank paths through an HMM? [closed]

I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path ...
1
vote
0answers
20 views

What is the maximal load of a “latency-bounded” Cuckoo Hash?

Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time. They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
24
votes
8answers
4k views

Computing the Levenshtein distance quickly

Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance. The naive approach is, ...
6
votes
2answers
249 views

Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
21
votes
5answers
2k views

Program for computing Tree decomposition of a graph

Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my ...
2
votes
0answers
79 views

On the goal of learned clause database reduction in CDCL SAT solvers

Modern SAT solvers frequently reduce the size of their learned clause database in order to keep its size as manageable as possible. This has as effect not to slow down the speed of unit propagations. ...
40
votes
8answers
6k views

Best Upper Bounds on SAT

In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT." I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
8
votes
2answers
252 views

Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
-1
votes
4answers
2k views

Interesting variation to the subset sum problem

An interesting variation of the subset sum problem was presented to me by a friend from work: Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) ...
10
votes
1answer
296 views

Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons? Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but ...
8
votes
2answers
1k views

Faster pseudo-polynomial time algorithms for PARTITION

I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or ...
5
votes
0answers
105 views

Lower bound for enumerating k closest pair of points

Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ ...
3
votes
0answers
43 views

Lower bound for reversing a list using queues

How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues? Each queue is FIFO. Time refers to the number of operations on the queues. ...
2
votes
1answer
1k views

Solve a simple system of linear inequalities in natural numbers

I want to find a solution to a system of linear inequalities of the following form \begin{aligned} a_1 + b &\ge a_2 \\\ \vdots \\\ a_4 + c &\ge a_1 \end{aligned} where $a_i \in \mathbb N \...
1
vote
1answer
388 views

Optimal value of a semidefinite program

Is a local optimum value of a SDP always the global one? If not, what are the conditions for that?
8
votes
2answers
738 views

SDP relaxation of independent set

I'm looking at page 28 of Lovasz "Semidefinite programs and combinatorial optimization" and it gives the following approximation of independence number of the graph $$\max u' Z u$$ subject to $$Z\...
58
votes
10answers
10k views

One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
10
votes
1answer
236 views

Algorithms on graphs represented using BDDs

The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong ...
3
votes
0answers
173 views

Complexity of the mandelbrot set on rationals

(Also posted on mathoverflow) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals. A point $c$ is contained within the Mandelbrot ...
8
votes
0answers
124 views

Finding $n$ many different primes efficiently

I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many ...
4
votes
0answers
488 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 ...
1
vote
1answer
86 views

What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?

I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.
14
votes
1answer
1k views

Deciding whether an interval contains a prime number

What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
5
votes
1answer
128 views

What does “hold uniformly” mean in the context of asymptotic analysis?

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):