The dynamic-programming tag has no wiki summary.
2
votes
1answer
112 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
93 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
201 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
226 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
362 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 ...
21
votes
0answers
541 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\}$.
...
32
votes
0answers
511 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
243 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
273 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
710 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
265 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
218 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
254 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 ...
