Scientific contributions of Leo Khachiyan (a short overview)
From MaRDI portal
Publication:944704
DOI10.1016/j.dam.2008.04.023zbMath1144.01305OpenAlexW1971647349MaRDI QIDQ944704
Endre Boros, Vladimir A. Gurvich
Publication date: 10 September 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.04.023
Cites Work
- A global parallel algorithm for the hypergraph transversal problem
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
- Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
- An inequality for the volume of inscribed ellipsoids
- On short paths interdiction problems: Total and node-wise limited interdiction
- Generating cut conjunctions in graphs and related problems
- Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
- A certain inequality for convex forms
- On the conductance of order Markov chains
- On the complexity of approximating the maximal inscribed ellipsoid for a polytope
- A greedy heuristic for a minimum-weight forest problem
- On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms
- On the complexity of approximating extremal determinants in matrices
- On the frequency of the most frequently occurring variable in dual monotone DNFs
- On the complexity of semidefinite programs
- Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
- On maximal frequent and minimal infrequent sets in binary matrices
- An inequality for polymatroid functions and its applications.
- Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
- Dual-bounded generating problems: Weighted transversals of a hypergraph
- Diagonal matrix scaling is NP-hard
- On the complexity of nonnegative-matrix scaling
- A sublinear-time randomized approximation algorithm for matrix games
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Integer optimization on convex semialgebraic sets
- Approximating fixed points of weakly contracting mappings
- Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
- On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
- On enumerating minimal dicuts and strongly connected subgraphs
- Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
- Approximate Max-Min Resource Sharing for Structured Concave Optimization
- The problem of calculating the volume of a polyhedron is enumerably hard
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
- Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Generating Minimal k-Vertex Connected Spanning Subgraphs
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Diagonal Matrix Scaling and Linear Programming
- Convergence rate of the game processes for solving matrix games
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- On the Complexity of Matrix Balancing
- Generating dual-bounded hypergraphs
- An Interior Point Method for Bordered Block-Diagonal Linear Programs
- An exponential‐function reduction method for block‐angular convex programs
- Rounding of Polytopes in the Real Number Model of Computation
- Coordination Complexity of Parallel Price-Directive Decomposition
- Algorithms and Computation
- Mathematical Foundations of Computer Science 2004
- ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
- Enumerating Spanning and Connected Subsets in Graphs and Matroids
- On the Complexity of Some Enumeration Problems for Matroids
- Mathematical Foundations of Computer Science 2005
- Integer Programming and Combinatorial Optimization
- Computing and Combinatorics
- Algorithms - ESA 2003
- Algorithms and Computation
- Generating all vertices of a polyhedron is hard
- LATIN 2004: Theoretical Informatics
- Generating all vertices of a polyhedron is hard
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
