Scientific contributions of Leo Khachiyan (a short overview)
---
paper_title: On the complexity of approximating the maximal inscribed ellipsoid for a polytope

paper_content:

We give a new polynomial bound on the complexity of approximating the maximal inscribed ellipsoid for a polytope.
---
paper_title: The polynomial solvability of convex quadratic programming

paper_content:

Abstract AN ACCURATE quadratic programming algorithm is constructed, in which the amount of work is bounded by a polynomial of the length of the recording of the problem in the binary number system.
---
paper_title: An Inequality for the Volume of Inscribed Ellipsoids

paper_content:

LetK be a convex body inRn, and letx* ? intK be the center of the ellipsoid of the maximal volume inscribed in the body. An arbitrary hyperplane throughx* cutsK into two convex bodiesK+ andK?. We show thatw(K±)/w(K)≤0.844..., wherew(·) is the volume of the inscribed ellipsoid.
---
paper_title: Complexity of Polytope Volume Computation

paper_content:

We survey some recent results on the complexity of computing the vol­ume of convex n-dimensional polytopes.
---
paper_title: Generating all vertices of a polyhedron is hard

paper_content:

We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open. Equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.
---
paper_title: Cyclic games and an algorithm to find minimax cycle means in directed graphs

paper_content:

Abstract An algorithm is described that finds optimal stationary strategies in dynamic two-person conflicts with perfect information, deterministic transitions, finite sets of positions, and time-averaged limiting integral payoff.
---
paper_title: On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction

paper_content:

Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ+ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor $c<10\sqrt{5}-21\approx1.36$ the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination.
---
paper_title: Extending Dijkstra's algorithm to maximize the shortest path by node-wise limited arc interdiction

paper_content:

We consider the problem of computing shortest paths in a directed arc-weighted graph G = (V,A) in the presence of an adversary that can block (interdict), for each vertex v ∈ V, a given number p(v) of the arcs Aout(v) leaving v. We show that if all arc-weights are non-negative then the single-destination version of the problem can be solved by a natural extension of Dijkstra's algorithm in time ::: ::: $$O(|A|+|V|{\rm log}|V|+\Sigma_{\upsilon\in{V}\ \backslash \{t\}}(|A_{out}(\upsilon)|-p(\upsilon)){\rm log}(p(\upsilon)+1)).$$ ::: ::: Our result can be viewed as a polynomial algorithm for a special case of the network interdiction problem where the adversary's budget is node-wise limited. When the adversary can block a given number p of arcs distributed arbitrarily in the graph, the problem (p-most-vital-arcs problem) becomes NP-hard. This result is also closely related to so-called cyclic games. No polynomial algorithm computing the value of a cyclic game is known, though this problem belongs to both NP and coNP.
---
paper_title: Cyclic games and an algorithm to find minimax cycle means in directed graphs

paper_content:

Abstract An algorithm is described that finds optimal stationary strategies in dynamic two-person conflicts with perfect information, deterministic transitions, finite sets of positions, and time-averaged limiting integral payoff.
---
paper_title: On the complexity of nonnegative-matrix scaling

paper_content:

An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.
---
paper_title: Approximate Max-Min Resource Sharing for Structured Concave Optimization

paper_content:

We present a Lagrangian decomposition algorithm which uses logarithmic potential reduction to compute an $\varepsilon$-approximate solution of the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. We show that this algorithm runs in $O(M(\varepsilon^{-2}+{\rm ln} M))$ iterations, a data independent bound which is optimal up to polylogarithmic factors for any fixed relative accuracy $\varepsilon\in(0,1)$. In the block-angular case, B is the product of K convex sets (blocks) and each constraint function is block separable. For such models, an iteration of our method requires a $\Theta(\varepsilon)$-approximate solution of K independent block maximization problems which can be computed in parallel.
---
paper_title: An Interior Point Method for Bordered Block-Diagonal Linear Programs

paper_content:

This paper presents an interior point method for solving a bordered block-diagonal linear program which consists of a number of disjoint blocks coupled by a total of $p$ variables and constraints. This structure includes the well-known block-angular and dual block-angular structures, as well as their special cases, such as staircase problems, generalized bounds, and multicommodity flows. When $p$ is small relative to the total dimension of the problem, the method achieves a substantial speedup relative to other general-purpose methods.
---
paper_title: An exponential‐function reduction method for block‐angular convex programs

paper_content:

An exponential potential-function reduction algorithm for convex block-angular optimization problems is described. These problems are characterized by K disjoint convex compact sets called blocks and M non-negative-valued convex block-separable coupling inequalities with a nonempty interior. A given convex block-separable function is to be minimized. Concurrent, minimum-cost, and generalized multicommodity network flow problems are important special cases of this model. The method reduces the optimization problem to two resource-sharing problems. The first of these problems is solved to obtain a feasible solution interior to the coupling constraints. Starting from this solution, The algorithm proceeds to solve the second problem on the original constraints, but with a modified exponential potential function. The method is shown to produce an ϵ-approximate solution in O(K(In M)(ϵ−2 + in K)) iterations, provided that there is a feasible solution sufficiently interior to the coupling inequalities. Each iteration consists of solving a subset of independent block problems, followed by a simple coordination step. Computational experiments with a set of large linear concurrent and minimum-cost multicommodity network flow problems suggest that the method can be practical for computing fast approximations to large instances.
---
paper_title: Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints

paper_content:

This paper presents block-coordinate descent algorithms for the approximate solution of large structured convex programming problems. The constraints of such problems consist of K disjoint convex compact sets $B^k $ called blocks, and M nonnegative-valued convex block-separable inequalities called coupling or resource constraints. The algorithms are based on an exponential potential function reduction technique. It is shown that feasibility as well as min-mix resource-sharing problems for such constraints can be solved to a relative accuracy $\varepsilon$ in $O( K\ln M ( \varepsilon^{ - 2} + \ln K ) )$ iterations, each of which solves K block problems to a comparable accuracy, either sequentially or in parallel. The same bound holds for the expected number of iterations of a randomized variant of the algorithm which uniformly selects a random block to process at each iteration. An extension to objective and constraint functions of arbitrary sign is also presented. The above results yield fast approximatio...
---
paper_title: Coordination complexity of parallel price-directive decomposition

paper_content:

The general block-angular convex resource sharing problem in K blocks and M nonnegative block-separable coupling constraints is considered. Applications of this model are in combinatorial optimization, network flows, scheduling, communication networks, engineering design, and finance. This paper studies the coordination complexity of approximate price-directive decomposition PDD for this problem, i.e., the number of iterations required to solve the problem to a fixed relative accuracy as a function of K and M. ::: ::: First a simple PDD method based on the classical logarithmic potential is shown to be optimal up to a logarithmic factor in M in the class of all PDD methods that work with the original unrestricted blocks. It is then shown that logarithmic and exponential potentials generate a polylogarithmically-optimal algorithm for a wider class of PDD methods which can restrict the blocks by the coupling constraints. ::: ::: As an application, the fastest currently-known deterministic approximation algorithm for minimum-cost multicommodity flows is obtained.
---
paper_title: Diagonal Matrix Scaling and Linear Programming

paper_content:

A positive semidefinite symmetric matrix either has a nontrivial nonnegative zero or can be scaled by a positive diagonal matrix into a doubly quasi-stochastic matrix. This paper describes a simple path-following Newton algorithm of the complexity $O(\sqrt{n} L)$ iterations to either scale an $n \times n$ matrix or give a nontrivial nonnegative zero. The latter problem is well known to be equivalent to linear programming.
---
paper_title: On The Complexity Of Matrix Balancing

paper_content:

An $n \times n$ matrix with nonnegative entries is said to be $balanced$ if for each $i=1,\dots,n$ the sum of the entries of its $i$th row is equal to the sum of the entries of its $i$th column. An $n \times n$ matrix $A$ with nonnegative entries is said to be $balancable$ $via$ $diagonal$ $similarity$ $scaling$ if there exists a diagonal matrix $X$ with positive diagonal entries such that $XAX^{-1}$ is balanced. We give upper and lower bounds on the entries of $X$ and prove the necessary sensitivity analysis in the required accuracy of the minimization of an associated convex programming problem. These results are used to prove the polynomial-time solvability of computing $X$ to any prescribed accuracy.
---
paper_title: On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms

paper_content:

We consider the well-known RAS algorithm for the problem of positive matrix scaling. We give a new bound on the number of iterations of the method for scaling a given d-dimensional matrix A to a prescribed accuracy. Although the RAS method is not a polynomial-time algorithm even for d=2, our bound implies that for any dimension d the method is a fully polynomial-time approximation scheme. We also present a randomized variant of the algorithm whose (expected) running time improves that of the deterministic method by a factor of d.
---
paper_title: On the Complexity of Approximating Extremal Determinants in Matrices

paper_content:

For a d × n matrix A, let B = B(A) be the set of all nondegenerate d × d submatrices (bases) of A, and let ?(A) = min{|det B| : B ? B}. We show that for any polynomial p = poly(d, n) in the dimension of A, the problem of approximating ?(A) within a factor of 2p is NP-hard. We also show that it is NP-hard to determine whether a set of n rational points in d dimensions is affinely or linearly degenerate. On the other hand, we give an algorithm for approximating ?(A) = max{|det B| : B ? B} within a factor of (1 + ?)d](d ? 1)/2 in O(nd2(??1 + log d + log log n)) arithmetic operations and comparisons over the reals.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: Computing integral points in convex semi-algebraic sets

paper_content:

Let Y be a convex set in R/sup k/ defined by polynomial inequalities and equations of degree at most d/spl ges/2 with integer coefficients of binary length l. We show that if Y/spl cap/Z/sup k//spl ne//spl theta/, then Y contains an integral point of binary length ld/sup O/((k/sup 4/)). For fixed k, our bound implies a polynomial-time algorithm for computing an integral point y/spl isin/Y. In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming.
---
paper_title: Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data

paper_content:

We show that |X| ≤ n|Y| must hold for two finite sets X, y ⊂ R n whenever they can be separated by a nonnegative linear function such that X is above Y and the componentwise minimum of any two distinct points in X is dominated by some point in y. As a consequence, we obtain an incremental quasi-polynomial time algorithm for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p-inefficient points of a given discrete probability distribution, and for generating all maximal hyper-rectangles which contain a specified fraction of points of a given set in R n . This provides a substantial improvement over previously known exponential time algorithms for these generation problems related to Integer and Stochastic Programming, and Data Mining. Furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, implying that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.
---
paper_title: Diagonal matrix scaling is NP-hard

paper_content:

Abstract A symmetric matrix A is said to be scalable if there exists a positive diagonal matrix X such that the row and column sums of XAX are all ones. We show that testing the scalability of arbitrary matrices is NP-hard. Equivalently, it is NP-hard to check for a given symmetric matrix A whether the logarithmic barrier function 1 2 x T Ax − ∑ ln x i has a stationary point in the positive orthant x > 0.
---
paper_title: Generating Paths and Cuts in Multi-pole (Di)graphs

paper_content:

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. For directed graphs both of these problems are NP-hard. We also give a polynomial delay algorithm for enumerating minimal sets of arcs connecting respectively two given nodes si and s 2 to a given vertex t 1 , and each vertex of a given subset of vertices T 2 .
---
paper_title: An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals

paper_content:

Given a finite set V , and a hypergraph H⊆ 2 V , the hyper- graph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practi- cal applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan (1996) gave an incremental quasi-polynomial time algorithm for solving the hypergraph transversal problem (9). In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same bound on the running time as in (9), practical experience with this im- plementation shows that it can be substantially faster. We also show that a slight modification of the algorithm in (9) can be used to give a stronger bound on the running time.
---
paper_title: Computing Many Maximal Independent Sets for Hypergraphs in Parallel

paper_content:

A hypergraph is called uniformly δ-sparse if for every nonempty subset X ⊆ V of vertices, the average degree of the sub-hypergraph of induced by X is at most δ. We show that there is a deterministic algorithm that, given a uniformly δ-sparse hypergraph , and a positive integer k, outputs k or all minimal transversals for in O(δlog(1 + k)polylog(δ|V|))-time using |V|O(logδ)kO(δ) processors. Equivalently, the algorithm can be used to compute in parallel k or all maximal independent sets for .
---
paper_title: An Efficient Implementation of a Joint Generation Algorithm

paper_content:

Let \(\mathcal{C}\) be an n-dimensional integral box, and π be a monotone property defined over the elements of \(\mathcal{C}\). We consider the problems of incrementally generating jointly the families \(\mathcal{F}_{\pi}\) and \(\mathcal{G}_{\pi}\) of all minimal subsets satisfying property π and all maximal subsets not satisfying property π, when π is given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time. In this paper, we present an efficient implementation of this procedure. We present experimental results to evaluate our implementation for a number of interesting monotone properties π.
---
paper_title: Dual-Bounded Generating Problems: Partial And Multiple Transversals Of A Hypergraph

paper_content:

We consider two generalizations of the notion of transversal to a finite hypergraph, the so-called multiple and partial transversals. Multiple transversals naturally arise in 0-1 programming, while partial transversals are related to data mining and machine learning. We show that for an arbitrary hypergraph the families of multiple and partial transversals are both dual-bounded in the sense that the size of the corresponding dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals for a given hypergraph are polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known dualization problem for hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal binary solutions for an arbitrary monotone system of linear inequalities.
---
paper_title: An intersection inequality for discrete distributions and related generation problems

paper_content:

Given two finite sets of points X, Y in Rn which can be separated by a nonnegative linear function, and such that the componentwise minimum of any two distinct points in X is dominated by some point in Y, we show that |X| = n|Y|. As a consequence of this result, we obtain quasi-polynomial time algorithms for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p-inefficient points of a given discrete probability distribution, and for generating all maximal empty hyper-rectangles for a given set of points in Rn. This provides a substantial improvement over previously known exponential algorithms for these generation problems related to Integer and Stochastic Programming, and Data Mining. Furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, which, for the very special case of one inequality, implies that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.
---
paper_title: On Enumerating Minimal Dicuts and Strongly Connected Subgraphs

paper_content:

We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given strongly connected directed graph G=(V,E). We show that the first of these problems can be solved in incremental polynomial time, while the second problem is NP-hard: given a collection of minimal dicuts for G, it is NP-hard to tell whether it can be extended. The latter result implies, in particular, that for a given set of points $\mathcal{A}\subseteq\mathbb{R}^{n}$, it is NP-hard to generate all maximal subsets of $\mathcal{A}$contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of $\mathcal{A}$whose convex hull contains the origin as an interior point, and show that this problem includes as a special case the well-known hypergraph transversal problem.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: Dual-Bounded Generating Problems: Weighted Transversals of a Hypergraph

paper_content:

Abstract We consider a generalization of the notion of transversal to a finite hypergraph, the so-called weighted transversals. Given a non-negative weight vector assigned to each hyperedge of an input hypergraph A and a non-negative threshold vector, we define a weighted transversal as a minimal vertex set which intersects all the hyperedges of A except for a sub-family of total weight not exceeding the given threshold vector. Weighted transversals generalize partial and multiple transversals introduced in Boros et al. (SIAM J. Comput. 30 (6) (2001)) and also include minimal binary solutions to non-negative systems of linear inequalities and minimal weighted infrequent sets in databases. We show that the hypergraph of all weighted transversals is dual-bounded, i.e., the size of its transversal hypergraph is polynomial in the number of weighted transversals and the size of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. For instance, we show that for any row-weighted m×n binary matrix and any threshold weight t, the number of maximal sets of columns whose row support has weight above t is at most m times the number of minimal sets of columns with row support of total weight below t. We also prove that the problem of generating all weighted transversals for a given hypergraph is polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known hypergraph dualization problem. As a corollary, we obtain an incremental quasi-polynomial-time algorithm for generating all weighted transversals for a given hypergraph. This result includes as special cases the generation of all the minimal Boolean solutions to a given system of non-negative linear inequalities and the generation of all minimal weighted infrequent sets of columns for a given binary matrix.
---
paper_title: An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension

paper_content:

We show that for hypergraphs of bounded edge size, the problem of extending a given list of maximal independent sets is NC-reducible to the computation of an arbitrary maximal independent set for an induced sub-hypergraph. The latter problem is known to be in RNC. In particular, our reduction yields an incremental RNC dualization algorithm for hypergraphs of bounded edge size, a problem previously known to be solvable in polynomial incremental time. We also give a similar parallel algorithm for the dualization problem on the product of arbitrary lattices which have a bounded number of immediate predecessors for each element.
---
paper_title: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

paper_content:

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that, for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.
---
paper_title: Dual-Bounded Hypergraphs: Generating Partial and Multiple Transversals

paper_content:

We consider two natural generalizations of the notion of transversal to a finite hypergraph, so called {\em multiple} and {\em partial} transversals. We show that the hypergraphs of all multiple and all partial transversals are dual-bounded in the sense that in both cases, the size of the dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals for a given hypergraph are polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known dualization problem for hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal Boolean solutions for an arbitrary monotone system of linear inequalities.
---
paper_title: On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs

paper_content:

Given a finite set V, and integers k≥1 and r≥0, let us denote by the class of hypergraphs with (k,r)-bounded intersections, i.e. in which the intersection of any k distinct hyperedges has size at most r. We consider the problem : given a hypergraph , and a subfamily of its maximal independent sets (MIS) , either extend this subfamily by constructing a new MIS or prove that there are no more MIS, that is . It is known that, for hypergraphs of bounded dimension , as well as for hypergraphs of bounded degree (where δ is a constant), problem can be solved in incremental polynomial time. In this paper, we extend this result to any integers k,r such that k+r=δ is a constant. More precisely, we show that for hypergraphs with k+r≤const, problem is NC-reducible to the problem of generating a single MIS for a partial subhypergraph of . In particular, this implies that is polynomial, and we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximally independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes , , and , where δ is a constant. We also show that, for , where k+r≤const, the problem of generating all MIS of can be solved in incremental polynomial-time and with space polynomial only in the size of .
---
paper_title: Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions

paper_content:

We consider monotone @?,@?-formulae @f of m atoms, each of which is a monotone inequality of the form f"i(x)>=t"i over the integers, where for i=1,...,m, f"i:Z^n@?R is a given monotone function and t"i is a given threshold. We show that if the @?-degree of @f is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying @f can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of m inequalities is NP-hard when m is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.
---
paper_title: An inequality for polymatroid functions and its applications

paper_content:

An integral-valued set function f:2v ↦ Z is called polymatroid if it is submodular, nondecreasing, and f(φ) = 0. Given a polymatroid function f and an integer threshold t ≥ 1, let α = α(f,t) denote the number of maximal sets X ⊆ V satisfying f(X) < t, let β = β(f,t) be the number of minimal sets X ⊆ V for which f(X) ≥ t, and let n = |V|. We show that if β ≥ 2 then α ≤ β(log t)/c, where c = c(n,β) is the unique positive root of the equation 1 = 2c(nc/log β - 1). In particular, our bound implies that α ≤ (nβ)log t for all β ≥ 1. We also give examples of polymatroid functions with arbitrarily large t, n, α and β for which α ≥ β(0.551 log t)/c. More generally, given a polymatroid function f : 2v ↦ Z and an integral threshold t ≥ 1, consider an arbitrary hypergraph H' such that |H'| ≥ 2 and f(H) ≥ t for all H ∈ H'. Let f' be the family of all maximal independent sets X of H' for which f(X) < t. Then |f'| ≤ |H'|(log t)/c(n,|H'|). As an application, we show that given a system of polymatroid inequalities f1(X) ≥ t1,..., fm(X) ≥ tm with quasi-polynomially bounded right-hand sides t1,....,tm, all minimal feasible solutions to this system can be generated in incremental quasi-polynomial time. In contrast to this result, the generation of all maximal infeasible sets is an NP-hard problem for many polymatroid inequalities of small range.
---
paper_title: Fourier-Motzkin Elimination Method.

paper_content:

Waste receptacles for use by animals, such as laboratory animals and household pets, are provided with an odor barrier of lightweight, non-absorbent, non-water-wettable, granular material, such as paraffin wax coated corn cob granules. The buoyant, non-absorbent, lightweight granular material is also useful as an odor barrier in liquid-containing portable human toilets and generally as an odor barrier for pools or sumps or open containers of odoriferous materials, such as aqueous offal wastes, aqueous waste from food processing plants and odoriferous wastes from other sources, such as industial sources, e.g., paper mills, chemical plants, manufacturing plants and the like. The non-absorbent granular material in animal toilet applications is conveniently retained on a foraminous tray which, in turn, is mounted on a collecting tray for collection of liquid waste percolating downwardly from the granular material into which the liquid waste was originally deposited.
---
paper_title: Generating Minimal k-Vertex Connected Spanning Subgraphs

paper_content:

We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k.
---
paper_title: On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices

paper_content:

Given an m×n binary matrix A, a subset C of the columns is called t-frequent if there are at least t rows in A in which all entries belonging to C are non-zero. Let us denote by α the number of maximal t-frequent sets of A, and let β denote the number of those minimal column subsets of A which are not t-frequent (so called t-infrequent sets). We prove that the inequality α≤(m−t+1)β holds for any binary matrix A in which not all column subsets are t-frequent. This inequality is sharp, and allows for an incremental quasi-polynomial algorithm for generating all minimal t-infrequent sets. We also prove that the analogous generation problem for maximal t-frequent sets is NP-hard. Finally, we discuss the complexity of generating closed frequent sets and some other related problems.
---
paper_title: Generating Dual-Bounded Hypergraphs

paper_content:

This article surveys some recent results on the generation of implicitly given hypergraphs and their applications in Boolean and integer programming, data mining, reliability theory, and combinatorics. Given a monotone property ~ over the subsets of a finite set V, we consider the problem of incrementally generating the family F π of all minimal subsets satisfying property ~ , when ~ is given by a polynomial-time satisfiability oracle. For a number of interesting monotone properties, the family F π turns out to be uniformly dual-bounded , allowing for the incrementally efficient enumeration of the members of F π. Important applications include the efficient generation of minimal infrequent sets of a database (data mining), minimal connectivity ensuring collections of subgraphs from a given list (reliability theory), minimal feasible solutions to a system of monotone inequalities in integer variables (integer programming), minimal spanning collections of subspaces from a given list (linear algebra) and max...
---
paper_title: On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets

paper_content:

Let A be an m × n binary matrix, t ? {1, ..., m} be a threshold, and ? > 0 be a positive parameter. We show that given a family of O(n?) maximal t-frequent column sets for A, it is NP-complete to decide whether A has any further maximal t-frequent sets, or not, even when the number of such additional maximal t-frequent column sets may be exponentially large. In contrast, all minimal t-infrequent sets of columns of A can be enumerated in incremental quasi-polynomial time. The proof of the latter result follows from the inequality ? ? (m-t+1)s, where ? and s are respectively the numbers of all maximal t-frequent and all minimal t-infrequent sets of columns of the matrix A. We also discuss the complexity of generating all closed t-frequent column sets for a given binary matrix.
---
paper_title: Generating all vertices of a polyhedron is hard

paper_content:

We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open. Equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.
---
paper_title: Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections

paper_content:

Given a finite set V, and integers k > 1 and r > 0, denote by A(k, r) the class of hypergraphs A ⊆ 2 V with (k, r)-bounded intersections, i.e. in which the intersection of any k distinct hyperedges has size at most r. We consider the problem MIS(A,I): given a hypergraph A and a subfamily I C I(A), of its maximal independent sets (MIS) I(A), either extend this subfamily by constructing a new MIS I ∈ I(A) \ I or prove that there are no more MIS, that is I = I(A). We show that for hypergraphs A E A(k,r) with k + r ≤ const, problem MIS(A,I) is NC-reducible to problem MIS(A',O) of generating a single MIS for a partial subhypergraph A' of A. In particular, for this class of hypergraphs, we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximal independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A(1, c), A(c, 0), and A(2,1), where c is a constant. We also show that, for A ∈ A(k,r), where k + r < const, the problem of generating all MIS of A can be solved in incremental polynomial-time with space polynomial only in the size of A.
---
paper_title: Generating all minimal integral solutions to monotone ∧,∨-systems of linear, transversal and polymatroid inequalities

paper_content:

We consider monotone ∨, ∧-formulae φ of m atoms, each of which is a monotone inequality of the form fi(x)≥ ti over the integers, where for i = 1,...,m, $f_i : \mathbb{Z}^n \mapsto \mathbb{R}$ is a given monotone function and ti is a given threshold. We show that if the ∨-degree of φ is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying φ can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of m inequalities is NP-hard when m is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.
---
paper_title: Rounding of polytopes in the real number model of computation

paper_content:

Let A be a set of m points in Rn. We show that the problem of 1 + en-rounding of A, i.e., the problem of computing an ellipsoid E ⊆ Rn such that [1 + en]-1E ⊆ conv. hullA ⊆ E, can be solved in Omn2e-1 + ln n + ln ln m arithmetic operations and comparisons. This result implies that the problem of approximating the minimum volume ellipsoid circumscribed about A can be solved in Om3.5 lnme-1 operations to a relative accuracy of e in the volume. The latter bound also applies to the 1 + en-rounding problem. Our bounds hold for the real number model of computation.
---
paper_title: On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions

paper_content:

Let f : {0,1} n → {0,1} be a monotone Boolean function whose value at any point x ∈ {0,1} n can be determined in time t. Denote by c=Λ I ∈ C ∨ i ∈ I x i the irredundant CNF off, where C is the set of the prime implicates of f. Similarly, let d=∨ J ∈ D Λ j ∈ J x j be the irredundant DNF of the same function, where D is the set of the prime implicants of f. We show that given subsets C' ⊆ C and D' ⊆ D such that (C',D') ¬= (C,D), a new term in (C\C')∪(D\D') can be found in time O(n(t+n))+m o(log m) , where m=|C'|+|D'|. In particular, if f(x) can be evaluated for every x ∈ {0,1} n in polynomial time, then the forms c and d can be jointly generated in incremental quasi-polynomial time. On the other hand, even for the class of Λ, ∨-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling from within the set of the prime implicates and implicants of f can be carried out in time bounded by a quasi-polynomial 2 polylog(.) in the input size of f. We also show that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D' =D or C' =C. This provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time. Such classes of monotone Boolean functions naturally arise in game theory, networks and relay contact circuits, convex programming, and include a subset of Λ, ∨-formulae of depth 3.
---
paper_title: On the frequency of the most frequently occurring variable in dual monotone DNFs

paper_content:

Abstract Let f ( X l ,…, X N )=⋁ I ∈ F ⋀ i ∈ I X i and g ( X l ,…, X N )=⋁ I ∈ G ⋀ i ∈ I X i be a pair of dual monotone irredundant disjunctive normal forms, where F and G are the sets of the prime implicants of tf and g , respectively. For a variable x i , i = 1, …, n , let μ i = # { I ∈ F | i ∈ I }/| F | and v i = # { I ∈ G | i ∈ I }/| G | be the frequencies with which x i occurs in f and g . It is easily seen that max { μ 1 , v 1 , …, μ n , v n } ⩾ 1/log(| F | + | G |). We give examples of arbitrarily large F and G for which the above bound is tight up to a factor of 2.
---
paper_title: Cubegrades: Generalizing Association Rules

paper_content:

Cubegrades are a generalization of association rules which represent how a set of measures (aggregates) is affected by modifying a cube through specialization (rolldown), generalization (rollup) and mutation (which is a change in one of the cube's dimensions). Cubegrades are significantly more expressive than association rules in capturing trends and patterns in data because they can use other standard aggregate measures, in addition to COUNT. Cubegrades are atoms which can support sophisticated “what if” analysis tasks dealing with behavior of arbitrary aggregates over different database segments. As such, cubegrades can be useful in marketing, sales analysis, and other typical data mining applications in business. ::: ::: In this paper we introduce the concept of cubegrades. We define them and give examples of their usage. We then describe in detail an important task for computing cubegrades: generation of significant cubes which is analogous to generating frequent sets. A novel Grid Based Pruning (GBP) method is employed for this purpose. We experimentally demonstrate the practicality of the method. We conclude with a number of open questions and possible extensions of the work.
---
paper_title: On the Complexity of Some Enumeration Problems for Matroids

paper_content:

Let $M$ be a matroid defined by an independence oracle on ground set $S$, and let $A\subseteq S$. We present an incremental polynomial-time algorithm for enumerating all minimal (maximal) subsets of $S$ which span (do not span) $A$. Special cases of these problems include the generation of bases, circuits, hyperplanes, flats of given rank, circuits through a given element, generalized Steiner trees, and multiway cuts in graphs, as well as some other applications. We also consider some tractable and NP-hard generation problems related to systems of polymatroid inequalities and (generalized) packing and spanning in matroids.
---
paper_title: An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

paper_content:

Given a finite set V, and a hypergraph H ⊆ 2V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.
---
paper_title: A global parallel algorithm for the hypergraph transversal problem

paper_content:

We consider the problem of finding all minimal transversals of a hypergraph H@?2^V, given by an explicit list of its hyperedges. We give a new decomposition technique for solving the problem with the following advantages: (i) Global parallelism: for certain classes of hypergraphs, e.g., hypergraphs of bounded edge size, and any given integer k, the algorithm outputs k minimal transversals of H in time bounded by polylog(|V|,|H|,k) assuming poly(|V|,|H|,k) number of processors. Except for the case of graphs, none of the previously known algorithms for solving the same problem exhibit this feature. (ii) Using this technique, we also obtain new results on the complexity of generating minimal transversals for new classes of hypergraphs, namely hypergraphs of bounded dual-conformality, and hypergraphs in which every edge intersects every minimal transversal in a bounded number of vertices.
---
paper_title: Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs

paper_content:

Let G=(V,E) be an undirected graph, and let B⊆V ×V be a collection of vertex pairs. We give an incremental polynomial time algorithm to enumerate all minimal edge sets X⊆E such that every vertex pair (s,t) ∈ B is disconnected in $(V,E \smallsetminus X)$, generalizing well-known efficient algorithms for enumerating all minimal s-t cuts, for a given pair s,t ∈ V of vertices. We also present an incremental polynomial time algorithm for enumerating all minimal subsets X⊆E such that no (s,t) ∈ B is a bridge in (V,X ∪ B). These two enumeration problems are special cases of the more general cut conjunction problem in matroids: given a matroid M on ground set S=E ∪ B, enumerate all minimal subsets X⊆E such that no element b ∈ B is spanned by $E \smallsetminus X$. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V,E ∪ B), the enumeration of cut conjunctions for vectorial matroids turns out to be NP-hard.
---
paper_title: Enumerating spanning and connected subsets in graphs and matroids

paper_content:

We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected edge subsets of a given graph can be generated in incremental polynomial time.
---
paper_title: Generating Partial and Multiple Transversals of a Hypergraph

paper_content:

We consider two natural generalizations of the notion of transversal to a finite hypergraph, arising in data-mining and machine learning, the so called multiple and partial transversals. We show that the hypergraphs of all multiple and all partial transversals are dual- bounded in the sense that in both cases, the size of the dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals of an arbitrary hypergraph are polynomial-time reducible to the well-known dualization problem of hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal Boolean solutions for an arbitrary monotone system of linear inequalities. Thus, it is unlikely that these problems are NP-hard.
---
paper_title: Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

paper_content:

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"1 and s"2 to, respectively, a given vertex t"1, and each vertex of a given subset of vertices T"2.
---
paper_title: Generating Weighted Transversals of a Hypergraph

paper_content:

We consider a generalization of the notion of transversal to a finite hypergraph, so called {\em weighted transversals}. Given a non-negative weight vector assigned to each hyperedge of the input hypergraph, we define a weighted transversal as a minimal vertex set which intersects a collection of hypereredges of sufficiently large total weight. We show that the hypergraph of all weighted transversals is dual-bounded, i.e, the size of its dual hypergraph is polynomial in the number of weighted transversals and the size of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. For instance, we show that for any threshold frequency, the number of maximal frequent sets of columns in a binary matrix is bounded by the number of minimal infrequent sets of columns in the same matrix multiplied by the number of its rows. We also prove that the problem of generating all weighted transversals for a given hypergraph is polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known hypergraph dualization problem. As a corollary, we obtain an incremental quasi-polynomial-time algorithm for generating all weighted transversals for a given hypergraph. This result includes as special cases the generation of all the minimal Boolean solutions to a given system of non-negative linear inequalities and the generation of all minimal infrequent sets of columns for a given binary matrix.
---
paper_title: Linear Scheduling is Nearly Optimal

paper_content:

This paper deals with the problem of finding optimal schedulings for uniform dependence algorithms. Given a convex domain, let Tf be the total time needed to execute all computations using the free (greedy) schedule and let Tl be the total time needed to execute all computations using the optimal linear schedule. Our main result is to bound Tl/Tf and Tl − Tf for sufficiently "fat" domains.
---

Title: Scientific contributions of Leo Khachiyan (a short overview)

Section 1: Linear and convex programming
Description 1: Summarize Khachiyan's breakthrough work on linear programming, particularly the ellipsoid method for solving linear inequalities in polynomial time.

Section 2: Enumeration and counting problems in LP
Description 2: Discuss Khachiyan's contributions to enumeration theory and the complexity of counting problems related to linear programming.

Section 3: Fictitious play and sublinear randomized approximation algorithm for matrix games
Description 3: Describe Khachiyan's research on the fictitious play method for matrix games and his development of sublinear randomized approximation algorithms.

Section 4: Cyclic games
Description 4: Review Khachiyan's work on cyclic games and mean payoff games, including his algorithms for computing values and strategies in these games.

Section 5: Isoperimetric inequalities and conductance of order Markov chains
Description 5: Explain Khachiyan's work on isoperimetric inequalities and their application to the conductance and mixing times of Markov chains.

Section 6: At Rutgers in the 90s
Description 6: Provide an overview of Khachiyan's research collaborations and key results during his tenure at Rutgers University in the 1990s.

Section 7: Approximating the extremal determinants is hard
Description 7: Detail Khachiyan's findings on the hardness of approximating extremal determinants and determining the degeneracy of points in geometry.

Section 8: Integer optimization on convex semialgebraic sets and semidefinite programming
Description 8: Summarize Khachiyan's work on extending integer programming results from polyhedra to convex semialgebraic sets and semidefinite programming.

Section 9: Enumeration problems
Description 9: Discuss Khachiyan's fundamental contributions to the complexity and algorithms for various enumeration problems, including dualization and joint generation.