We investigate the following greedy approach to attack linear programs of type $$\max \{1^{T} x\mid l\le Ax\le u\}$$ max { 1 T x ∣ l ≤ A x ≤ u } where A has entries in $$\{-1,0,1\}$$ { - 1 , 0 , 1 } : The greedy algorithm starts with a feasible solution x and, iteratively, chooses an improving variable and raises it until some constraint becomes tight. In the special case, where A is the edge-path incidence matrix of some digraph $$G=(V,E)$$ G = ( V , E ) , and $$l=0$$ l = 0 , this greedy algorithm corresponds to the Ford–Fulkerson algorithm to solve the max ( s , t )-flow problem in G w.r.t. edge-capacities u. It is well-known that the Ford–Fulkerson algorithm always terminates with an optimal flow, and that the number of augmentations strongly depends on the choice of paths in each iteration. The Edmonds–Karp rule that prefers paths with fewer arcs leads to a running time of at most $$|E|^2$$ | E | 2 augmentations. The paper investigates general types of matrices A and preference rules on the variables that make the greedy algorithm efficient. In this paper, we identify conditions that guarantee for the greedy algorithm not to cycle, and/or optimality of the greedy algorithm, and/or to yield a quadratic (in the number of rows) number of augmentations. We illustrate our approach with flow and circulation problems on regular oriented matroids.

While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations M1, M2resp. two QRW parametrizations Q1, Q2in time O(|Σ| max(N1, N2)4), where N1,N2are the number of hidden states in M1, M2resp. the dimension of the state spaces associated with Q1, Q2, and Σ is the set of output symbols. Previously avail able algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subrou tines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.

We present greedy algorithms for some classes of combinatorial packing and cover problems within the general formal framework of Hoffman and Schwartz' lattice polyhedra. Our algorithms compute in a first phase Monge solutions for the associated dual cover and packing problems and then proceed to construct greedy solutions for the primal problems in a second phase. We show optimality of the algorithms under certain sub- and supermodular assumptions and monotone constraints. For supermodular lattice polyhedra with submodular constraints, our algorithms offer the farthest reaching generalization of Edmonds' polymatroid greedy algorithm currently known.

The notion of the evolution of a discrete random source with finite alphabet is introduced and its behavior under the action of an associated linear evolution operator is studied. Viewing these sources as possibly stable dynamical systems it is proved that all random sources with finite evolution dimension are asymptotically mean stationary, which implies that such random sources have ergodic properties and a well-defined entropy rate. It is shown that the class of random sources with finite evolution dimension properly generalizes the well-studied class of finitary stochastic processes, which includes (hidden) Markov sources as special cases.

MOTIVATION: DNA microarrays allow the simultaneous measurement of thousands of gene expression levels in any given patient sample. Gene expression data have been shown to correlate with survival in several cancers, however, analysis of the data is difficult, since typically at most a few hundred patients are available, resulting in severely underdetermined regression or classification models. Several approaches exist to classify patients in different risk classes, however, relatively little has been done with respect to the prediction of actual survival times. We introduce CASPAR, a novel method to predict true survival times for the individual patient based on microarray measurements. CASPAR is based on a multivariate Cox regression model that is embedded in a Bayesian framework. A hierarchical prior distribution on the regression parameters is specifically designed to deal with high dimensionality (large number of genes) and low sample size settings, that are typical for microarray measurements. This enables CASPAR to automatically select small, most informative subsets of genes for prediction. RESULTS: Validity of the method is demonstrated on two publicly available datasets on diffuse large B-cell lymphoma (DLBCL) and on adenocarcinoma of the lung. The method successfully identifies long and short survivors, with high sensitivity and specificity. We compare our method with two alternative methods from the literature, demonstrating superior results of our approach. In addition, we show that CASPAR can further refine predictions made using clinical scoring systems such as the International Prognostic Index (IPI) for DLBCL and clinical staging for lung cancer, thus providing an additional tool for the clinician. An analysis of the genes identified confirms previously published results, and furthermore, new candidate genes correlated with survival are identified.

A binpacking game is a cooperative N-person game, where the set of players consists of k bins of size 1 and n items of sizes a 1 ,..., a n . The value of a coalition of bins and items is the maximum total size of items in the coalition that can be packed into the bins of the coalition. Our main result asserts that for every $\epsilon > 0$, there exist $\epsilon$-approximate core allocations provided k is large enough. Moreover, for every fixed $\delta > 0$, the smallest $\epsilon$ for which the $\epsilon$-approximate core of a given binpacking game is nonempty can be computed in polynomial time with error at most $\delta$, provided k is sufficiently large. We furthermore derive more specialized results for some subclasses of binpacking games.

Given an ordering of the variables according to nonincreasing coefficients of the objective function $c^T x$, the nonnegative matrix A is said to be greedy if, under arbitrary nonnegative constraint vectors b and h, the greedy algorithm maximizes $c^T x$ subject to $Ax \leq b,0 \leq x \leq h$. Extending a result of Hoffman, Kolen, and Sakarovitch for $(0,1)$-matrices, we characterize greedy matrices in terms of forbidden submatrices, which yields polynomial recognition algorithms for various classes of greedy matrices. The general recognition problem for the existence of forbidden submatrices is shown to be NP-complete.

During recent years, much work has gone into the exploration of general fundamental principles underlying local search strategies for combinatorial optimization. Many of these strategies can be subsumed under the general framework of Tabu Search, which introduces mechanisms of guidance and control based on flexible memory processes, broadening the range of strategic possibilities beyond those incorporated in memoryless search heuristics such as Simulated Annealing. We consider some examples of such memory based strategies for modifying both the generation and acceptance probabilities and investigate their impact on convergence results. It turns out that several Tabu Search ideas can be subjected to mathematical analyses similar to those applied to Simulated Annealing, making it possible to establish corresponding convergence properties based on a broader foundation. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

How many questions are needed to decide whether an unknown ordered set is isomorphic to a fixed ordered set $P_0 $? This recognition problem is considered, together with some related computational problems concerning ordered sets.

Linial and Saks [2] have shown that $O(\log N)$ evaluations of an order preserving map $f:p \to \mathbb{R}$ are necessary and sufficient to determine whether $\alpha \in f(P)$, where N is the number of ideals of N and $\alpha \in \mathbb{R}$ is a given real number. In this paper, we investigate the problem of how to perform the evaluations so that Linial and Saks’ bound is guaranteed, and solve the problem for the classes of interval and series-parallel orders and hence, in particular, for rooted trees. We observe that the greedy-type binary search algorithm, which is optimal for chains, already need not be optimal for general rooted trees. We furthermore discuss the computational complexity of the general search problem and obtain results indicating that the general problem might be hard.

The optimization problem for linear functions on finite languages is studied, and an (almost) complete characterization of those functions for which a primal and a dual greedy algorithm work well with respect to a canonically associated linear programming problem is given. The discussion in this paper is within the framework of ordered languages, and the characterization uses the notion of rank feasibility of a weighting with respect to an ordered language. This yields a common generalization of a sufficient condition, obtained recently by Korte and Lovász for greedoids, and the greedy algorithm for ordered sets in Faigel's paper [6]. Ordered greedoids are considered the appropriate generalization of greedoids, and the connection is established between ordered languages, polygreedoids, and Coxeteroids. Answering a question of Björner, the author shows in particular that a polygreedoid is a Coxeteroid if and only if it is derived from an integral polymatroid.

Construction of classes of ordered sets are given for which the setup minimization problem can be solved by an efficient algorithm. Those constructions generalize series-parallel connections. Special classes of ordered sets are exhibited for which the greedy algorithm yields an optimal linear extension. In particular, it is shown that the class of N-free ordered sets is both defect optimal and strongly greedy.