MPI-INF Logo

MPI-INF D1 Publications

Search the publication database
.
Return

Your search returned the following 26 documents:

  1. On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets
    Khaled M. Elbassioni, Kazuhisa Makino, Kurt Mehlhorn, and Fahimeh Ramezani
    In: 19th Annual International Computing and Combinatorics Conference (COCOON-13), Hangzhou, China, 2013, 65-76
  2. Every Stochastic Game with Perfect Information Admits a Canonical Form
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Springer
  3. 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
  4. 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
  5. Finding Simplices containing the Origin in Two and Three Dimensions
    Khaled Elbassioni, Amr Elmasry, and Kazuhisa Makino
    International Journal of Computational Geometry & Applications 21 (5): 495-506, 2011
  6. On the readability of monotone Boolean formulae
    Khaled Elbassioni, Kazuhisa Makino, and Imran Rauf
    Journal of Combinatorial Optimization 22 (3): 293-304, 2011
  7. 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
  8. 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
  9. Left-to-right multiplication for monotone Boolean dualization
    Endre Boros, Khaled Elbassioni, and Kazuhisa Makino
    SIAM Journal on Computing 39 (7): 3424-3439, 2010
  10. On effectivity functions of game forms
    Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
    Games and Economic Behavior 68 (2): 512-531, 2010
  11. 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

  12. On the Readability of Monotone Boolean Formulae
    Khaled Elbassioni, Kazuhisa Makino, and Imran Rauf
    In: Computing and Combinatorics :15th Annual International Conference, COCOON 2009, Niagara Falls, New York, USA, 2009, 496-505
    [PDF: Download: cocoon09.pdf]
  13. Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
    Khaled Elbassioni, Kazuhisa Makino, and Imran Rauf
    In: Algorithms - ESA 2009 : 17th Annual European Symposium, Copenhagen, Denmark, 2009, 143-154
    [PDF: Download: esa09.pdf]
  14. 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
  15. 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
  16. 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
  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. 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
  22. 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
  23. 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]
  24. 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]
  25. 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]
  26. 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