Homepage
Khaled Elbassioni
Max-Planck-Institut für Informatik
Department 1:Algorithms and Complexity
Campus E1 4, Room 307
66123 Saarbrücken
Germany
elbassio @ .... (this domain-name)
Phone: +49 681 9325 107
Fax: +49 681 9325 199
Approximation algorithms, combinatorial optimization, enumeration algorithms, game theory
Optimization II (winter semester 09/10)
Optimization (summer semester 09)
Internet Economics (summer semester 08)
Discrete Optimization (summer semester 07)
Approximation Algorithms (winter semester 05/06)
My publications in the MPII database
Journal Publications:
- On effectivity functions of game forms, to appear in Games and Economic Behaviour, (with E. Boros, V. Gurvich and K. Makino)
- Improved Approximations for Guarding 1.5-Dimensional Terrains, to appear in Algorithmica, (with E. Krohn, D. Matijevic, J. Mestre and D. Severdija).
- The Negative Cycles Polyhedron and Hardness of Checking Some Polyhedral Properties, Annals of Operations Research, to appear, (with E. Boros, V. Gurvich and H. R. Tiwary)
- Algorithms for Dualization over Products of Partially Ordered Sets, SIAM Journal on Discrete Mathematics, to appear
- A Note on Systems With Max-min and Max-product Constraints, Fuzzy Sets and Systems, 159(17): 2272-2277 (2008)
- Simultaneous Matchings: Hardness and Approximation, Journal of Computer and System Sciences, 74(5): 884-897 (2008)
(with Irit Katriel, Martin Kutz and Meena Mahajan).
- On the Complexity of Monotone Dualization and Generating Minimal Hypergraph Transversals, Discrete Applied Mathematics, 156(11): 2109-2123 (2008)
- On short paths interdiction problems: Total and node-wise limited interdiction, Theory of Computing Systems, 43(2): 204-233 (2008),
(with Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich, Gabor Rudolf and Jihui Zhao)
- Enumerating Spanning and Connected Subsets in Graphs and Matroids, Journal of the Operations Research Society of Japan, to appear,
(with Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich and Kazuhisa Makino)
- Approximation Algorithms for the Euclidean Traveling Salesman Problem with Discrete and Continuous Neighborhoods, International Journal of Computational Geometry and Applications (invited contribution), to appear,
(with Aleksei Fishkin and Rene Sitters).
- Upper Bound on the Number of Vertices of Polyhedra with $0,1$-Constraint Matrices, Information Processing Letters 100(2):69--71 (with Zvi Lotker and Raimund Seidel).
- Multiconsistency and Robustness with Global Constraints, Constraints 11(4):335--352, 2006 (with with Irit Katriel).
- Generating All Vertices of a Polyhedron is Hard, To appear in Discrete and Computational Geometry (Invited contribution)
(with Leonid Khachiyan, Endre Boros, Konrad Borys and Vladimir Gurvich).
- Transversal Hypergraphs to Perfect Matchings in Bipartite Graphs: Characterization and Generation Algorithms, Journal of Graph Theory (with Endre Boros and Vladimir Gurvich).
- On the Complexity of Some Enumeration Problems for
Matroids, SIAM Journal on Discrete Math (with Endre Boros, Vladimir Gurvich, Leonid Khachiyan and kazuhisa Makino).
- Dual-bounded Generating Problems:
Efficient and Inefficient Points for Discrete Probability Distributions and
Sparse Boxes for Multidimensional Data, Theoretical Computer Scince 379(3):361--376, 2007 (Invited contribution) (with Endre Boros, Vladimir Gurvich, Leonid Khachiyan and kazuhisa Makino).
- On Dualization of Hypergraphs with Bounded Edge-Intersections and Other Related Classes of Hypergraphs, Theoretical Computer Scince 382(2):139--150, 2007 (Invited contribution) (with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
- An Efficient Implementation of a Quasi-Polynomial Algorithm for Generating Hypergraph Transversals and its
application in Joint Generation,
to appear in Discrete Applied Math (with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
- Enumerating Disjunctions and Conjunctions of Paths and Cuts in Reliability Theory,
to appear in Discrete Applied Math (Invited contribution) (with Endre Boros, Vladimir Gurvich, Leonid Khachiyan and kazuhisa Makino).
- An Indexing Method for Answering Queries on Moving Objects, Distributed and Parallel Databases. 17(3)(2005), pp. 215--249.
(with Amr Elmasry and Ibrahim Kamel).
- 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)(2003), pp. 355--368.(with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
- An Inequality for Polymatroid Functions and its Applications, Discrete Applied Mathematics. 131(2)(2003), pp. 255--281.
(with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
- Dual-Bounded Generating Problems: All Minimal Integer Solutions for a
Monotone System of Linear Inequalities, SIAM Journal on Computing. 31 (5) (2002), pp. 1621-1643.
(with Endre Boros, Vladimir Gurvich, Leonid Khachiyan and Kazuhisa Makino).
- Generating Dual-Bounded Hypergraphs, Optimization Methods and Software. 17(5)(2002), pp. 749--781.(with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
- An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension, Parallel Processing Letters. 10 (4) (2000) pp. 253-266.
(with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
in Refereed Proceedings
- A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics, SODA 10 (to appear), (with H. Chan)
- Complexity of Computing the Vertex Centroid of a Polyhedron, ISAAC 09 (to appear), (with H. R. Tiwary)
- On Profit-Maximizing Pricing for the Highway and Tollbooth Problems, SAGT 09, (with R. Raman, S. Ray and R. Sitters).
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs, ESA 09, (with K. Makino and I. Rauf).
- On the Readability of Monotone Boolean Formulae, COCOON 09, (with K. Makino and I. Rauf).
- Improved Approximations for Guarding 1.5-Dimensional Terrains, STACS 09, (with E. Krohn, D. Matijevic, J. Mestre and D. Severdija).
- On the Approximability of the Maximum Feasible Subsystem Problem with 0/1-Coefficients, SODA 09, (with R. Raman, S. Ray and R. Sitters).
- On Berge Multiplication for Monotone Boolean Dualization, ICALP 08, (with E. Boros and K. Makino).
- Approximating the Interval Constrained Coloring Problem, SWAT 08. (with E. Althaus, S. Canzar, A. Karrenbauer and J. Mestre).
- Some fixed-parameter tractable classes of $\DUAL$ and related problems, IWPEC 08, (with M. Hagen and I. Rauf).
- On the Complexity Checking Self-duality of Polytopes and its Relation to Vertex Enumeration and Graph Isomorphism, SoCG 08, (with H. R. Tiwary).
- Computer-generated Theorems on Nash-solvability of Bimatrix Games Based on Excluding Certain $2 \times 2$ Subgames., CSR 08 (with E. Boros, V. Gurvich, K. Makino and V. Oudalov).
- A Quasi-PTAS for Profit Maximizing Pricing on Line Graphs, ESA 07. (with Rene Sitters and Yan Zhang).
- Conflict-Free Coloring for Rectangle Ranges Using $\tilde{O}(n^{.382+\epsilon})$ Colors, SPAA 07. (with Deepak Ajwani, Sathish Govindarajan and Saurabh Ray).
- Generating Minimal k-Vertex Connected Spanning Subgraphs,, COCOON 07. (with Endre Boros, Konrad Borys, Vladimir Gurvich, Kazuhisa Makino and Gbor Rudolf).
- On Approximating the TSP with intersecting Neighborhoods, ISAAC 06. (with Aleksei V. Fishkin and Rene Sitters).
- On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization, ESA 06.
- Enumerating Spanning and Connected Subsets in Graphs and Matroids, ESA 06. (with Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich and Kazuhisa Makino).
- Finding all minimal infrequent multi-dimensional intervals, LATIN 06.
- Conflict-Free Colorings of Rectangle Ranges, STACS 06. (with Nabil H. Mustafa).
- Generating All Vertices of a Polyhedron is Hard, SODA 06. (with Leonid Khachiyan, Endre Boros, Konrad Borys and Vladimir Gurvich).
- Generating cut conjunctions and bridge avoiding extensions in graphs, ISAAC 05. to appear.
(with Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich and Kazuhisa Makino).
- Simultaneous Matchings ISAAC 2005. (with Irit Katriel, Martin Kutz and Meena Mahajan).
- Generating All Minimal Integral Solutions to Monotone $\wedge,\vee$-Systems of Linear, Transversal and Polymatroid Inequalities, MFCS 05. (with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
- A New Algorithm for the Hypergraph Transversal Problem, COCOON 05. (with Endre Boros, Vladimir Gurvich and Leonid Khachiyan).
- Output-Sensitive Algorithms for Enumerating and Counting Simplices Containing a Given Point in the Plane, CCCG 05. (with Amr Elmasry).
- Approximation Algorithms for Euclidean Group TSP, ICALP 05. (with Aleksei V. Fishkin, Nabil H. Mustafa and Rene Sitters).
- Multiconsistency and Robustness with Global Constraints, CP-AI-OR 2005. (with Irit Katriel).
- Generating Paths and Cuts in Multi-pole (Di)graphs. MFCS 2004 (with Endre Boros, Vladimir Gurvich, Leonid Khachiyan and Kazuhisa Makino).
- Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems ESA 2004 (with Endre Boros and Vladimir Gurvich).
- Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems, IPCO 2004 (with Endre Boros, Vladimir Gurvich, and Leonid Khachiyan).
- An Intersection Inequality for Discrete Distributions and Related Generation Problems, ICALP 2003. (with Endre Boros, Vladimir Gurvich, Leonid Khachiyan and Kazuhisa Makino).
- On Dualization in Products of Forests, STACS 2002.
- An Efficient Indexing Scheme for Multi-Dimensional Moving Objects, ICDT 2003. (with Amr Elmasry and Ibrahim Kamel).
Ph.D. Thesis (Advisor: Leonid Khachiyan):
Master's Thesis
- Parallelization of Loops with Non-uniform Dependencies, Alexandria University, Egypt, June 1995.
B.S. in Computer Science, Alexandria University, Egypt, June 1992.
