MPI-INF Logo
  • Home
  • MPI-INF D1 Publications, generated: 9:57, 30 November 2023

MPI-INF D1 Publications

Search the publication database
.
Return

Your search returned the following 45 documents:

  1. Every Stochastic Game with Perfect Information Admits a Canonical Form
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Springer
  2. On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Discrete Mathematics 312 (4): 772-788, 2012
  3. A lower bound for discounting algorithms solving two-person zero-sum limit average payoff stochastic games
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    . Note: unpublished
  4. Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
    Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, and Bodo Manthey
    In: Automata, Languages and Programming : 38th International Colloquium, ICALP 2011, Zurich, Switzerland, 2011, 147-158
  5. The negative cycles polyhedron and hardness of checking some polyhedral properties
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Hans Raj Tiwary
    Annals of Operations Research 188 (1): 63-76, 2011
  6. A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    In: Integer Programming and Combinatorial Optimization : 14th International Conference, IPCO 2010, Lausanne, Switzerland, 2010, 341-354
  7. On effectivity functions of game forms
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Games and Economic Behavior 68 (2): 512-531, 2010
  8. On Nash Equilibria and Improvement Cycles in Pure Positional Strategies for Chess-like and Backgammon-like $n$-person Games
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino

  9. A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2x2 subgames
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino, and Vladimir Oudalov
    In: Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, 2008, 99-109
  10. Characterization of the vertices and extreme directions of the negative cycle polyhedron and hardness of generating vertices of 0/1-polyhedra
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Hans Raj Tiwary
    CoRR abs/0801.3790, 2008
  11. Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Discrete Applied Mathematics 156 (11): 2020-2034, 2008
  12. Generating All Vertices of a Polyhedron Is Hard
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich
    Discrete & Computational Geometry 39 (1-3): 174-190, 2008
  13. Generating Cut Conjunctions in Graphs and Related Problems
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Algorithmica 51 (3): 239-263, 2008
  14. On Enumerating Minimal Dicuts and Strongly Connected Subgraphs
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Algorithmica 50 (1): 159-172, 2008
  15. On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf, and Jihui Zhao
    Theory Comput. Syst. 43 (2): 204-233, 2008
  16. A global parallel algorithm for the hypergraph transversal problem
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Information Processing Letters 101 (4): 148-155, 2007
  17. Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Theoretical Computer Science 379 (3): 361-376, 2007
  18. Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Discrete Applied Mathematics 155 (2): 137-149, 2007
  19. Generating Minimal k-Vertex Connected Spanning Subgraphs
    Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino, and Gabor Rudolf
    In: Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Proceedings, Banff, Canada, 2007, 222-231
  20. Generating Vertices of Polyhedra and Related Monotone Generation Problems
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino

  21. On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Theoretical Computer Science 382 (2): 139-150, 2007
  22. Enumerating Spanning and Connected Subsets in Graphs and Matroids
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    In: Algorithms - ESA 2006, 14th Annual European Symposium, Zürich, Switzerland, 2006, 444-455
  23. Generating All Vertices of a Polyhedron is Hard
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06, Miami, FL, USA, 2006, 758-765
  24. A New Algorithm for the Hypergraph Transversal Problem
    Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Computing and combinatorics : 11th Annual International Conference, COCOON 2005, Kunming, China, 2005, 767-776
  25. Generating All Minimal Integral Solutions to Monotone $\wedge,\vee$-Systems of Linear, Transversal and Polymatroid Inequalities
    Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Mathematical Foundations of Computer Science 2005 : 30th International Symposium, MFCS 2005, Gdansk, Poland, 2005, 556-567
  26. Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs
    Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Algorithms and computation : 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, 2005, 156-165
  27. On the Complexity of Some Enumeration Problems for Matroids
    Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    SIAM Journal on Discrete Mathematics 19 (4): 966-984, 2005
  28. Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
    Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich
    In: Algorithms – ESA 2004: 12th Annual European Symposium, Bergen, Norway, 2004, 122-133
    [PDF: Download: ESA04.pdf]
  29. An Efficient Implementation of a Joint Generation Algorithm
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: Experimental and efficient algorithms : Third International Workshop, WEA 2004, Angra dos Reis, Brazil, 2004, 114-128
    [PDF: Download: WAE04.pdf]
  30. Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: Integer programming and combinatorial optimization : 10th International IPCO Conference, New York, NY, USA, 2004, 152-162
    [PDF: Download: IPCO04.pdf]
  31. Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, 2004, 488-498
    [PDF: Download: LATIN04.pdf]
  32. Generating Paths and Cuts in Multi-pole (Di)graphs
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino
    In: Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004, Prague, Czech Republic, 2004, 298-309
    [PDF: Download: MFCS04.pdf]
  33. Algorithms for Enumerating Circuits in Matroids.
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan
    In: Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, 2003, 485-494
    [PDF: Download: ISAAC2003.pdf]
  34. An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    In: Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, 2003, 556-567
    [PDF: Download: ESA03.pdf]
  35. An Inequality for Polymatroid Functions and its Applications
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Discrete Applied mathematics 131: 27 p., 2003

  36. An Intersection Inequality for Discrete Distributions and Related Generation Problems
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino
    In: Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, 2003, 543-555
    [PDF: Download: ICALP03.pdf]
  37. Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Mathematical Programming, Ser. B 98 (1-3): 14 p., 2003

  38. Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, Vladimir Gurvich, and Kazuhisa Makino
    SIAM Journal on Computing 31: 20 p., 2002

  39. Generating Dual-Bounded Hypergraphs
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Optimization Methods and Software 17 (5): 33 p., 2002
    [PS: Download: oms.ps]
  40. Generating Dual-Bounded Hypergraphs
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Optimization Methods and Software 17 (5): 33 p., 2002
    [PS: Download: oms.ps]
  41. Matroid Intersections, Polymatroid Inequalities, and Related Problems
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    In: Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, 2002, 143-154
    [PDF: Download: MFCS02.pdf]
  42. On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, Vladimir Gurvich, and Kazuhisa Makino
    In: Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Heraklion, Crete, Greece, 2001, 92-103
    [PDF: Download: icalp01.pdf]
  43. An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension
    Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Parallel Processing Letters 10 (4): 14 p., 2000

  44. On repetition-free Boolean functions
    Vladimir Gurvich
    Uspekhi Mat. Nauk. (Russian Math. Surveys) 32: 183-184, 1977. Note: (in Russian)
  45. Criteria for repetition-freeness of functions in the algebra of logic
    Vladimir Gurvich
    Soviet Math. Dokl. 43 (3): 721-726, 1991