# Tagged Questions

The tag has no usage guidance.

105 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 ...
171 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 ...
37 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 ...
169 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. ...
245 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 ...
457 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 algorithmic,...
62 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, ...
304 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 ...
21 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 ...
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 ...
212 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 ...
262 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 ...
364 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$ ...
105 views

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 ...
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\}$. ...
945 views

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 ...
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 ...
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 ...