Undiscretized dynamic programming and ordinal embeddings

Many optimization problems which are known to be NP-hard on graphs are polynomially solvable on trees using dynamic programming. Dynamic programming typically involves recursive functions stored as tables. Each entry of the table corresponds to the optimal subproblem solution. In many applications the complexity of brute-force dynamic programming can be improved especially when the functions involved are sparse, convex or concave. Algorithms for speeding up dynamic programming on path-like one dimensional structures are known. Here, we “undiscretize” the functions i.e. represent them as functions of continuous variable instead of storing the functions as the tables of discrete values. We use efficient data structures to store such functions and show how to quickly carry out operations involving these functions. We improve the complexity bounds for many tree dynamic programming problems, typically, from O(n2) to O(n log n). These include problems like facility location, covering, economic lot sizing and multicast filtering.; Given a set of pairwise distances on a set of n points, constructing an edge-weighted tree whose leaves are these i points such that the tree distances would mimic the original distances under some criteria is a fundamental problem in computational biology. This problem can also be seen as hierarchical clustering or as an embedding into additive (tree) metric spaces. In ordinal embeddings, the distance preservation criterion is to preserve the total or partial order of the pairwise distances. We show that the problem of finding a weighted tree, if it exists, which would preserve the total order on pairwise distances is NP-hard. A partial order on pairwise distances between points which orders all distances that share an end point is equivalent to an order where the distances in each triangle are ordered. This order, called triangle order, has been studied in biological settings. We also show the NP-hardness of the problem of finding the weighted tree which would preserve a triangle order. This answers a long standing open problem considered extensively by computational biologists.