(Technical Report CSD-870067, December 1987)
D. Stott Parker
We introduce a programming paradigm in which statements are constraints over partial orders. A partial order programming problem has the formminimize u subject to u1 >= v1 u2 >= v2 ...where u is the goal, and u1 >= v1, ... is a collection of constraints called the program. A solution of the problem is a minimal value for u determined by values for u1,v1, etc. satisfying the constraints. The domain of values here is a partial order, a domain D with ordering relation >=. The partial order programming paradigm has interesting properties:
- It generalizes mathematical programming, dynamic programming, and computer programming paradigms (logic, functional, and others) cleanly, and offers a foundation both for studying and combining paradigms.
- It takes thorough advantage of known results for continuous funtionals on complete partial orders, when the constraints involve expressions using only continuous and monotone operators. These programs have an elegant semantics coinciding with recent results on the relaxation solution method for constraint problems.
- It presents a framework that may be effective in modeling of complex systems, and in knowledge representation for cognitive computation problems.
(Technical Report CSD-960003, November 1994; issued March 1996; revised and expanded August 1997)
D. Stott Parker, Prasad Ram
Modern analyses of greedy-solvable problems (in terms of matroids, greedoids, submodularity, etc.) have grown in sophistication to the point that uninitiated readers can come away with a sense of confusion and disbelief. Despite the sophistication of these analyses and the great importance of greedy algorithms, currently there appears to be no truly satisfactory resolution of what a greedy algorithm is, or when and why greedy algorithms work. The pervasiveness of greedy algorithms is due to their simplicity, so it is disturbing that an arcane theory would be required to explain them.
Our contribution here is a new theory, giving a simple linear algebraic framework of greed. First, we introduce a generalized majorization ordering on numeric sequences, and identify conditions for functions on sequences to preserve this ordering. Generalized majorization is not a total order, but a preorder. It is naturally viewed as an `exchange' ordering where the exchanges are specific linear transformations. Second, we show that greedy-solvable problems can be formalized as optimization problems in which the objective is monotone with respect to this exchange ordering. We outline greedy algorithms for such problems, including those that exploit additional properties of the objective, such as convexity. Examples from the literature illustrate how diverse well-known applications of greed can be expressed.
(Technical Report CSD-960038, October 1996; revised and expanded September 1997)
D. Stott Parker, Prasad Ram
We show that the space of all binary Huffman codes for a finite alphabet defines a lattice, ordered by the imbalance of the code trees. Representing code trees as path-length sequences, we show that the imbalance ordering is closely related to a majorization ordering on real-valued sequences that correspond to discrete probability density functions. Furthermore, this tree imbalance is a partial ordering that is consistent with the total orderings given by either the external path length (sum of tree path lengths), or the entropy determined by the tree structure. On the imbalance lattice, we show the weighted path-length of a tree (the usual objective function for Huffman coding) is a submodular function, as is the corresponding function on the majorization lattice. Submodular functions are discrete analogues of convex functions. These results give perspective on Huffman coding, and suggest new approaches to coding as optimization over a lattice.
(Technical Report CSD-970036, September 1997)
D. Stott Parker, Prasad Ram
Majorization is an important partial order on multisets. Since its development at the turn of the twentieth century by economists formalizing the notion of `exchange' among distributions, it has found applications ranging from stochastic scheduling to singular value theory.
In this paper we reconstruct majorization as a partial order on vectors (ordered sequences) using linear algebra. We do this in two different ways, one following a recent extension of majorization to permit partial ordering among the indices of the sequences, and the other following a model of majorization as `exchangeability'. Majorization with respect to a partial order is shown to be a special case of majorization as exchangeability. In this special case, the resulting majorization order always defines a distributive lattice that is isomorphic to the standard real vector lattice.
In classical majorization theory, the semigroup of doubly-stochastic matrices plays a crucial role, both in the definition of majorization and in the modeling of exchange. We generalize majorization to permit any matrix semigroup of exchanges. Various semigroups of stochastic matrices make particularly interesting kinds of exchanges, and simultaneously define useful notions of majorization.
Finally, we investigate notions of convexity. When the functions in question are differentiable, we show that both Schur convexity and submodularity can be reexpressed naturally in this linear algebraic formulation.