The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
0answers
100 views

Beating naive dynamic programming: examples similar to integer partitions?

Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming ...
9
votes
0answers
169 views

Monotone circuit complexity of matroids?

Call a monotone boolean function $f$ a matroid function if its minterms are bases of some matroid. I am interested in monotone circuit complexity of such functions, even when we "tie hands" of these ...
0
votes
0answers
36 views

Structural properties of Markov decision processes

My question is about structural properties of Markov decision processes (MDPs). In particular, I am interested in partially observable MDPs, or POMDPs, and what can be said about their optimal ...
-1
votes
2answers
164 views

Dynamic Programming vs Greedy Algorithm

In (Sniedovich 2006) "Dijkstra's algorithm revisited: the dynamic programming connexion", Sniedovich provides us another interpretation of Dijkstra's algorithm as a dynamic programming implementation. ...
14
votes
1answer
243 views

Monotone arithmetic circuit complexity of elementary symmetric polynomials?

The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables. I am interested in the monotone arithmetic $(+,\times)$ circuit ...
15
votes
1answer
453 views

Is Dynamic Programming never weaker than Greedy?

In the circuit complexity, we have separations between powers of various circuit models. In the proof complexity, we have separations between powers of various proof systems. But in the ...
3
votes
0answers
59 views

Counting words of length $n$ in an inherently ambiguous CFG?

There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, ...
11
votes
1answer
297 views

Covering string by palindromes

Given a string $w=\sigma_1\sigma_2\ldots\sigma_n$, a palindrome cover is a sequence $p_1p_2\cdots p_m$ of words $p_i$ such that $p_1p_2\cdots p_m = w$ and such that each $p_i$ is a palindrome. How ...
1
vote
0answers
20 views

Which matrix of Q values is being used here?

This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task In section 2.1, equations (5) and (6), I am wondering which Q values are ...
4
votes
0answers
82 views

What is the current “state-of-the-art” solver for quadratic knapsack problems?

New to this forum, so please let me know if my question format is incorrect. For linear KP with $n$ items and $c$ capacity, dynamic programming can find exact solutions in $\mathcal{O}(nc)$. I have ...
0
votes
0answers
210 views

How to solve such a graph optimization problem?

I have a graph optimization problem which is hard to describe in the title. There is a component based system which consists of components and data transmissions between components(components and ...
10
votes
0answers
260 views

a geometric variant of k-medians. NP-hard or in P?

The following problem is a special case of k-medians. Is it NP-hard? Is it in P? Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$. Output: a ...
15
votes
1answer
362 views

Can short-distance connectivity be harder than connectivity?

Has anybody seen the following (or similar) question being considered: Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the presence/absence of short $s$-$t$ ...
3
votes
1answer
105 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 | ...
1
vote
0answers
186 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 ...
-2
votes
1answer
418 views

Liner time complexity for wordwrap problem [closed]

Can some body explain me how to apply memoization technique to achieve linear time complexity for bellow. http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/
5
votes
0answers
124 views

Evidence of non P-hard problems that require polynomial space?

It is admitted that a $\mathsf{P}$-complete problem requires polynomial space and thus cannot be efficiently parallelized. One purpose of these problems is that they can be used to 'defeat' an ...
0
votes
0answers
140 views

Calculating exact/approximate solution to a formula

Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$. Consider ...
4
votes
1answer
71 views

Bellman principle and approximability

Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
1
vote
4answers
207 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: ...
-6
votes
1answer
2k views

Dynamic programming and Divide and conquer approach [closed]

How does Dynamic Programming differ from Divide and conquer approach for solving problems? Can anyone explain the essential idea of Dynamic Programming. Thanks for any help.
2
votes
0answers
201 views

extension for Levenshtein distance

I am looking for an extension for Levenshtein distance (Edit distance) for multi dimensional strings (2D and 3D). I am not sure if there is a formal definition for multi dimensional or not, but here ...
6
votes
0answers
657 views

Euclidean TSP algorithms

Are there any known exact algorithms for Euclidean TSP that take advantage of the inherent structure of the problem? Do any of these algorithms have better asymptotics than $O(2^n n^2)$ of a DP ...
5
votes
1answer
296 views

Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming

For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$. This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) ...
4
votes
1answer
348 views

Problem understanding “connectivity” characteristic for the $k$-connected subgraph problem

I am reading this article, and I am having trouble to understand the 11th definition (page 7) about the connectivity characteristic. I do understand the raw ...
2
votes
1answer
139 views

Computing unique subset intersections

Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S? As per @JeffE's comment below, there are edge ...
3
votes
2answers
257 views

Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum

This question arose from a discussion between a friend and I. $A$ is a sequence of length $T$ where for any $a_i$ in $A$, $a_i \in \left\{{1, 2, 3}\right\}$ $B$ is a sequence of length $U$ where ...
1
vote
0answers
308 views

How can I find all numbers for which the XOR-sum is 0?

Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied: $x_1 \oplus x_2 \oplus ...
8
votes
2answers
600 views

Is there some mathematical closed form (or somewhat tight asymptotic one) for “Google Eggs Puzzle”?

The following brief description of the known "Google Eggs Puzzle" comes mainly from the web site Google Eggs: Google Eggs Puzzle: Given n floors and m eggs, what is the approach to find the ...
24
votes
0answers
2k views

Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

Roughly speaking, my question is: How costly is to make a cyclic graph acyclic while preserving all simple $s$-$t$ paths? Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$. ...
37
votes
0answers
940 views

Monotone complexity of s-t connectivity

In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide whether there is a path between all $n^2$ pairs ...
7
votes
1answer
330 views

Does this bin packing problem have a name?

My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a ...
1
vote
0answers
356 views

Converting a bounded knapsack problem to 0/1 knapsack problem

I originally posted this question at the programmers section of StackExchange (because that section is supposed to deal with data structures and algorithms), but they suggested posting in the math ...
3
votes
2answers
1k views

Dynamic programming and shortest path problem

Several months back, I asked in math.SE the following question I wonder if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source ...
1
vote
0answers
360 views

Cannot understand the problem of Bitonic Euclidean Traveling-Salesman [closed]

I am referring to the problem in Introduction to Algorithms. I kind of fail to understand the problem. From what I see, I need to sort the x-coordinates of the given set of points and then form a ...
6
votes
0answers
293 views

Embedded dynamic programming (and planar subgraph isomorphism)

In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
0
votes
1answer
267 views

Variable profit knapsack [closed]

sorry for bad formatting earlier We are given Cx,i, Cy,i, Cz,i ∈ ℕ and Px,i, Py,i, Pz,i > 0 for i=1,2,3 such that Px,1 < Px,2 < Px,3, Py,1 < Py,2 < Py,3, and Pz,1 < Pz,2 < Pz,3. We ...