Leonid Khachiyan

According to our database1, Leonid Khachiyan authored at least 61 papers between 1990 and 2009.

Collaborative distances:



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


Fourier-Motzkin Elimination Method.
Proceedings of the Encyclopedia of Optimization, Second Edition, 2009

On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction.
Theory Comput. Syst., 2008

Generating All Vertices of a Polyhedron Is Hard.
Discret. Comput. Geom., 2008

Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions.
Discret. Appl. Math., 2008

On Enumerating Minimal Dicuts and Strongly Connected Subgraphs.
Algorithmica, 2008

Generating Cut Conjunctions in Graphs and Related Problems.
Algorithmica, 2008

Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data.
Theor. Comput. Sci., 2007

On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs.
Theor. Comput. Sci., 2007

Computing Many Maximal Independent Sets for Hypergraphs in Parallel.
Parallel Process. Lett., 2007

A global parallel algorithm for the hypergraph transversal problem.
Inf. Process. Lett., 2007

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory.
Discret. Appl. Math., 2007

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation.
Discret. Appl. Math., 2006

Enumerating Spanning and Connected Subsets in Graphs and Matroids.
Proceedings of the Algorithms, 2006

Extending Dijkstra's Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction.
Proceedings of the Computer Science, 2006

On the Complexity of Some Enumeration Problems for Matroids.
SIAM J. Discret. Math., 2005

Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

A New Algorithm for the Hypergraph Transversal Problem.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

Dual-bounded generating problems: weighted transversals of a hypergraph.
Discret. Appl. Math., 2004

An Efficient Implementation of a Joint Generation Algorithm.
Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

Generating Paths and Cuts in Multi-pole (Di)graphs.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2004

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices.
Math. Program., 2003

An inequality for polymatroid functions and its applications.
Discret. Appl. Math., 2003

On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices.
Ann. Math. Artif. Intell., 2003

Algorithms for Enumerating Circuits in Matroids.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

An Intersection Inequality for Discrete Distributions and Related Generation Problems.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals.
Proceedings of the Algorithms, 2003

Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities.
SIAM J. Comput., 2002

Generating dual-bounded hypergraphs.
Optim. Methods Softw., 2002

Cubegrades: Generalizing Association Rules.
Data Min. Knowl. Discov., 2002

On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Matroid Intersections, Polymatroid Inequalities, and Related Problems.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Approximate Max-Min Resource Sharing for Structured Concave Optimization.
SIAM J. Optim., 2001

On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph.
SIAM J. Comput., 2000

An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension.
Parallel Process. Lett., 2000

Integer Optimization on Convex Semialgebraic Sets.
Discret. Comput. Geom., 2000

Generating Partial and Multiple Transversals of a Hypergraph.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Approximating Fixed Points of Weakly Contracting Mappings.
J. Complex., 1999

On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions.
Discret. Appl. Math., 1999

On the Complexity of Semidefinite Programs.
J. Glob. Optim., 1997

On the frequency of the most frequently occurring variable in dual monotone DNFs.
Discret. Math., 1997

Computing Integral Points in Convex Semi-algebraic Sets.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

An Interior Point Method for Bordered Block-Diagonal Linear Programs.
SIAM J. Optim., 1996

Approximate minimum-cost multicommodity flows in Õ(epsilon<sup>-2</sup>KNM) time.
Math. Program., 1996

Rounding of Polytopes in the Real Number Model of Computation.
Math. Oper. Res., 1996

Coordination Complexity of Parallel Price-Directive Decomposition.
Math. Oper. Res., 1996

On the Complexity of Dualization of Monotone Disjunctive Normal Forms.
J. Algorithms, 1996

A sublinear-time randomized approximation algorithm for matrix games.
Oper. Res. Lett., 1995

An exponential-function reduction method for block-angular convex programs.
Networks, 1995

On the Complexity of Approximating Extremal Determinants in Matrices.
J. Complex., 1995

Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints.
SIAM J. Optim., 1994

On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms.
Oper. Res. Lett., 1993

A greedy heuristic for a minimum-weight forest problem.
Oper. Res. Lett., 1993

On the complexity of approximating the maximal inscribed ellipsoid for a polytope.
Math. Program., 1993

Diagonal Matrix Scaling and Linear Programming.
SIAM J. Optim., 1992

Linear scheduling is close to optimality.
Proceedings of the Application Specific Array Processors, 1992

Linear Scheduling Is Nearly Optimal.
Parallel Process. Lett., 1991

An Inequality for the Volume of Inscribed Ellipsoids.
Discret. Comput. Geom., 1990