Database Entry Point
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF D1 Publications, generated: 13:41, 23 May 2013

Search the publication database

  . Return

Your search returned the following 44 documents:

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

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

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

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

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

  41. Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Generating Dual-Bounded Hypergraphs
    Optimization Methods and Software 17 (5): 33 p., 2002
    [PS: Download: oms.ps]
  42. Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    Matroid Intersections, Polymatroid Inequalities, and Related Problems
    In: Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, 2002, 143-154
    [PDF: Download: MFCS02.pdf]
  43. Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, and Vladimir Gurvich
    An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension
    Parallel Processing Letters 10 (4): 14 p., 2000

  44. Endre Boros, Khaled M. Elbassioni, Leonid Khachiyan, Vladimir Gurvich, and Kazuhisa Makino
    On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
    In: Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Heraklion, Crete, Greece, 2001, 92-103
    [PDF: Download: icalp01.pdf]