MPI-INF Logo

MPI-INF D1 Publications

Search the publication database
.
Return

Your search returned the following 44 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. Improved Approximations for Guarding 1.5-Dimensional Terrains
    Khaled M. Elbassioni, Erik Krohn, Domagoj Matijevic, Julián Mestre, and Domagoj Severdija
    Algorithmica Online First: 1-13, 2009
  3. A Quasi-PTAS for Envy-free Pricing on Line Graphs
    Khaled M. Elbassioni, Rene Sitters, and Yan Zhang

    [PS: Download: htp.ps]
  4. Conflict-Free Coloring for Rectangle Ranges Using $\tildeO(n^.382+\epsilon)$ Colors
    Deepak Ajwani, Khaled M. Elbassioni, Sathish Govindarajan, and Saurabh Ray
    In: 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 07), San Diego, CA, USA, 2007. Note: To Appear
  5. Generating Vertices of Polyhedra and Related Monotone Generation Problems
    Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino

  6. Conflict-Free Colorings of Rectangle Ranges
    Khaled M. Elbassioni and Nabil H. Mustafa
    In: STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, 2006, 254-263
  7. 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
  8. Finding All Minimal Infrequent Multi-dimensional Intervals
    Khaled M. Elbassioni
    In: LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, 2006, 423-434
  9. 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
  10. Multiconsistency and Robustness with Global Constraints
    Khaled M. Elbassioni
    Constraints 11 (4): 335-352, 2006
  11. On Approximating the TSP with Intersecting Neighborhoods
    Khaled M. Elbassioni, Aleksei V. Fishkin, and Rene Sitters
    In: Algorithms and Computation : 17th International Symposium, ISAAC 2006, Kolkata, India, 2006, 213-222
  12. On the Complexity of Monotone Boolean Duality Testing
    Khaled M. Elbassioni
    DIMACS, Piscataway, DIMACS TR: 2006-01
  13. On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
    Khaled M. Elbassioni
    In: Algorithms - ESA 2006, 14th Annual European Symposium, Zürich, Switzerland, 2006, 340-351
  14. Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices
    Khaled M. Elbassioni, Zvi Lotker, and Raimund Seidel
    Information Processing Letters 100 (2): 69 - 71, 2006
  15. 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
  16. An Indexing Method for Answering Queries on Moving Objects
    Khaled M. Elbassioni, Amr Elmasry, and Ibrahim Kamel
    Distributed and Parallel Databases 17 (3): 215-249, 2005
  17. Approximation algorithms for Euclidean Group TSP
    Khaled M. Elbassioni, Aleksei V. Fishkin, Nabil H. Mustafa, and Rene Sitters
    In: Automata, languages and programming : 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, 2005, 1115-1126
  18. Conflict-Free Colorings of Rectangle Ranges for Wireless Networks
    Khaled M. Elbassioni and Nabil H. Mustafa

    [PS: Download: rectangles.ps]
  19. 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
  20. 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
  21. Multiconsistency and Robustness with Global Constraints
    Khaled M. Elbassioni and Irit Katriel
    In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems : Second International Conference, CPAIOR 2005, Prague, Czech Republic, 2005, 168-182
  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. Output-Sensitive Algorithms for Enumerating and Counting Simplices Containing a Given Point in th Plane
    Amr Elmasry and Khaled M. Elbassioni
    In: 17th Canadian Conference on Computational Geometry (CCCG'05), Windsor, Canada, 2005, 248-251
  24. Simultaneous Matchings
    Khaled M. Elbassioni, Irit Katriel, Martin Kutz, and Meena Mahajan
    In: Algorithms and computation : 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, 2005, 106-115
  25. 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]
  26. 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]
  27. 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]
  28. 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]
  29. 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]
  30. Scalable Multimedia Disk Scheduling
    Mohamed F. Mokbel, Walid G. Aref, Khaled M. Elbassioni, and Ibrahim Kamel
    In: 20th International Conference on Data Engineering, ICDE 2004, Boston, USA, 2004, 498-509
    [PDF: Download: ICDE04.pdf]
  31. 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]
  32. 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]
  33. An Efficient Indexing Scheme for Multi-dimensional Moving Objects
    Khaled M. Elbassioni, Amr Elmasry, and Ibrahim Kamel
    In: Database Theory - ICDT 2003, 9th International Conference, Siena, Italy, 2003, 425-439
    [PDF: Download: ICDT03.pdf]
  34. 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

  35. 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]
  36. 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

  37. An Algorithm for Dualization in Products of Lattices and Its Applications
    Khaled M. Elbassioni
    In: Algorithms - ESA 2002, 10th Annual European Symposium, Rome, Italy, 2002, 424-435
    [PDF: Download: ESA02.pdf]
  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 Dualization in Products of Forests.
    Khaled M. Elbassioni
    In: STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, 2002, 142-153
    [PDF: Download: stacs02.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 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]