Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

Preperfect graphs

We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs.     

A Dynamic location problem for graphs

We introduce a class of optimization problems, calleddynamic location problems, involving the processing of requests that occur sequentially at the nodes of a graphG. This leads to the definition of a new parameter of graphs, called the window indexWX(G), that measures how large a window into the future is needed to solve every instance of the dynamic location problem onG optimally on-line. We completely characterize this parameter:WX(G)k if and only ifG is a weak retract of a product of complete graphs of size at mostk. As a byproduct, we obtain two (polynomially recognizable) structural characterizations of such graphs, extending a result of Bandelt.     

On Timonov's algorithm for global optimization of univariate Lipschitz functions

Timonov proposes an algorithm for global maximization of univariate Lipschitz functions in which successive evaluation points are chosen in order to ensure at each iteration a maximal expected reduction of the region of indeterminacy, which contains all globally optimal points. It is shown that such an algorithm does not necessarily converge to a global optimum.     

Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison

We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P: find a globally-optimal value off and a corresponding point; Problem Q: find a set of disjoint subintervals of [a, b] containing only points with a globally-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P. In phase I, this algorithm obtains rapidly a solution which is often globally-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.     

Optimal partitions having disjoint convex and conic hulls

LetA ¹,,A ⁿ be distinctk-dimensional vectors. We consider the problem of partitioning these vectors intom sets so as to maximize an objective which is a quasi-convex function of the sum of vectors in each set. We show that there exists an optimal partition whose sets have (pairwise) disjoint conic hulls. We also show that if the number of vectors in each of the sets is constrained, then a weaker conclusion holds, namely, there exists an optimal partition whose sets have (pairwise) disjoint convex hulls. The results rely on deriving necessary and sufficient conditions for a point to be an extreme point of a corresponding polytope.Research of this author was partially supported by NSF Grant ECS-83-10213 and by a Grant for the Promotion of Research at the Technion.     

Using an iterative linear solver in an interior-point method for generating support vector machines

This paper concerns the generation of support vector machine classifiers for solving the pattern recognition problem in machine learning. A method is proposed based on interior-point methods for convex quadratic programming. This interior-point method uses a linear preconditioned conjugate gradient method with a novel preconditioner to compute each iteration from the previous. An implementation is developed by adapting the object-oriented package OOQP to the problem structure. Numerical results are provided, and computational experience is discussed.     

Entropy, independent sets and antichains: A new approach to Dedekind's problem

For -regular, -vertex bipartite graphs with bipartition , a precise bound is given for the sum over independent sets of the quantity . (In other language, this is bounding the partition function for certain instances of the hard-core model.) This result is then extended to graded partially ordered sets, which in particular provides a simple proof of a well-known bound for Dedekind's Problem given by Kleitman and Markowsky in 1975.

     

A Solution to a Problem of Jacobson,Kézdy and Lehel

We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k²–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85)