Leonid Khachiyan | Academic Influence

Leonid Khachiyan's AcademicInfluence.com Rankings

Leonid Khachiyan

Mathematics

#1038

World Rank

#1774

Historical Rank

Measure Theory

#2816

World Rank

#3354

Historical Rank

mathematics Degrees

Download Badge

Mathematics

Leonid Khachiyan's Degrees

PhD Mathematics Moscow State University

Why Is Leonid Khachiyan Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Leonid Genrikhovich Khachiyan was a Soviet and American mathematician and computer scientist. He was most famous for his ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time. Even though this algorithm was shown to be impractical, it has inspired other randomized algorithms for convex programming and is considered a significant theoretical breakthrough.

(See a Problem?)

Leonid Khachiyan's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Polynomial algorithms in linear programming (1980) (1588)
On the Complexity of Dualization of Monotone Disjunctive Normal Forms (1996) (457)
The polynomial solvability of convex quadratic programming (1980) (361)
Rounding of Polytopes in the Real Number Model of Computation (1996) (270)
Generating All Vertices of a Polyhedron Is Hard (2006) (181)
On the complexity of approximating the maximal inscribed ellipsoid for a polytope (1993) (165)
Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints (1994) (150)
On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions (1999) (142)
A sublinear-time randomized approximation algorithm for matrix games (1995) (135)
On the conductance of order Markov chains (1991) (129)
On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction (2008) (113)
Coordination Complexity of Parallel Price-Directive Decomposition (1996) (112)
Cubegrades: Generalizing Association Rules (2002) (111)
On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets (2002) (108)
On the Complexity of Semidefinite Programs (1997) (95)
Linear Scheduling Is Nearly Optimal (1991) (89)
On the Complexity of Approximating Extremal Determinants in Matrices (1995) (76)
On the Complexity of Some Enumeration Problems for Matroids (2005) (76)
ON THE COMPLEXITY OF NONNEGATIVE-MATRIX SCALING (1996) (73)
Approximate Max-Min Resource Sharing for Structured Concave Optimization (2000) (69)
Integer Optimization on Convex Semialgebraic Sets (2000) (68)
Complexity of Polytope Volume Computation (1993) (67)
Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities (2002) (61)
An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension (2000) (61)
An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation (2006) (57)
An exponential-function reduction method for block-angular convex programs (1995) (50)
On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices (2003) (48)
Diagonal Matrix Scaling and Linear Programming (1992) (47)
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections (2004) (45)
Approximate minimum-cost multicommodity flows in $$\tilde O$$ (ɛ−2KNM) timetime (1996) (42)
Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph (2001) (40)
On the Complexity of Matrix Balancing (1997) (39)
Linear scheduling is close to optimality (1992) (37)
A greedy heuristic for a minimum-weight forest problem (1993) (35)
COMMUNICATIONS OF THE MOSCOW MATHEMATICAL SOCIETY: The problem of calculating the volume of a polyhedron is enumerably hard (1989) (33)
A global parallel algorithm for the hypergraph transversal problem (2007) (32)
Enumerating Spanning and Connected Subsets in Graphs and Matroids (2006) (30)
An Intersection Inequality for Discrete Distributions and Related Generation Problems (2003) (26)
A New Algorithm for the Hypergraph Transversal Problem (2005) (26)
An inequality for polymatroid functions and its applications (2003) (25)
Computing integral points in convex semi-algebraic sets (1997) (25)
Fourier-Motzkin Elimination Method (2009) (24)
Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems (2004) (22)
Approximating Fixed Points of Weakly Contracting Mappings (1999) (22)
An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals (2003) (21)
On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms (1993) (20)
Extending Dijkstra's Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction (2006) (19)
On Enumerating Minimal Dicuts and Strongly Connected Subgraphs (2007) (19)
Generating Partial and Multiple Transversals of a Hypergraph (2000) (18)
Generating dual-bounded hypergraphs (2002) (18)
Algorithms for Enumerating Circuits in Matroids (2003) (18)
On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs (2007) (17)
Transversal Hypergraphs and Families of Polyhedral Cones (2001) (17)
Generating Cut Conjunctions in Graphs and Related Problems (2008) (17)
On the frequency of the most frequently occurring variable in dual monotone DNFs (1997) (15)
Computing Many Maximal Independent Sets for Hypergraphs in Parallel (2007) (14)
Enumerating disjunctions and conjunctions of paths and cuts in reliability theory (2007) (14)
Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs (2005) (13)
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities (2001) (13)
Dual-bounded generating problems: weighted transversals of a hypergraph (2004) (12)
Diagonal matrix scaling is NP-hard (1996) (12)
An Interior Point Method for Bordered Block-Diagonal Linear Programs (1996) (12)
Convergence rate of the game processes for solving matrix games (1977) (11)
Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data (2007) (10)
An inequality for the volume of inscribed ellipsoids (1990) (10)
Generating Paths and Cuts in Multi-pole (Di)graphs (2004) (10)
On the exact solution of systems of linear inequalities and linear programming problems (1982) (9)
Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices (2003) (9)
Matroid Intersections, Polymatroid Inequalities, and Related Problems (2002) (6)
Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions (2008) (6)
Dual-Bounded Hypergraphs: A Survey∗ (2002) (4)
An inequality limiting the number of maximal frequent sets (2000) (4)
An Efficient Implementation of a Joint Generation Algorithm (2004) (4)
Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities (2005) (4)
On the complexity of real and integer semidefinite programming (1997) (3)
Enumerating Cut Conjunctions in Graphs and Related Problems 1 , 2 by (2005) (3)
Chapter IV. Complexity of Polytope Volume Computation (1993) (2)
in Graphs and Related Problems (2007) (1)
An interactive procedure based on the inscribed ellipsoid method (1990) (1)
Approximate Minimum-cost Multicommodity Flows in ~ O(" 02 Kn M ) Time 2;3 Approximate Minimum-cost Multicommodity Flows in ~ O(" 02 Kn M ) Time* (1995) (1)
Dual - Bounded Generating Problems : An Intersection Inequality for Discrete Distributions and Its Applications (2003) (0)
Coordination complexity of parallel Lagrangian decomposition (1994) (0)
Approximate Minimum-cost Multicommodity Flows in $\tilde 0(\eps^{-2}KNM)$ Time (1995) (0)
Weighted Transversals of a Hypergraph (2001) (0)

This paper list is powered by the following services:

Other Resources About Leonid Khachiyan

en.wikipedia.org

What Schools Are Affiliated With Leonid Khachiyan?

Leonid Khachiyan is affiliated with the following schools:

Image Attributions

Image Source for Leonid Khachiyan