MPI-INF Logo
  • Home
  • MPI-INF D1 Publications, generated: 9:55, 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. Left-to-right multiplication for monotone Boolean dualization
    Endre Boros, Khaled Elbassioni, and Kazuhisa Makino
    SIAM Journal on Computing 39 (7): 3424-3439, 2010
  8. On effectivity functions of game forms
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Games and Economic Behavior 68 (2): 512-531, 2010
  9. 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

  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. On Berge Multiplication for Monotone Boolean Dualization
    Endre Boros, Khaled Elbassioni, and Kazuhisa Makino
    In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, 2008, 48-59
  16. On Enumerating Minimal Dicuts and Strongly Connected Subgraphs
    Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich
    Algorithmica 50 (1): 159-172, 2008
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. Generating Vertices of Polyhedra and Related Monotone Generation Problems
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino

  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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]
  31. 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]
  32. 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]
  33. 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]
  34. 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]
  35. 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]
  36. 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]
  37. 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

  38. 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]
  39. 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

  40. 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

  41. 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]
  42. 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]
  43. 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]
  44. 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

  45. 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]