Endre Boros

 

Director of RUTCOR

Rutgers Center for Operations Research

640 Bartholomew Road                                                                                                                                

Piscataway, NJ 08854-8003

Room 123

Tel:       (732) 445-3041                    

Fax:      (732) 445-5472                               

e-mail:  Endre dot Boros at rutcor.rutgers.edu

Education

MS. in Mathematics, Eotvos Lorand University, Budapest, Hungary, 1978;

Thesis title: On Sperner Spaces; advisor: Ferenc Karteszi

Doctorate (Ph.D.) in Mathematics, Eotvos Lorand University, Budapest, Hungary, 1985;

Thesis title: Surrogate Constraints in 0-1 Programming; advisor: Andras Prekopa

Editorial Activities

Editor-in-Chief of Discrete Applied Mathematics (2007- ) and of Annals of Operations Research (2007- ).

Associate Editor of the Annals of Mathematics and Artificial Intelligence (1999-).

Member of the Editorial Boards of Computational Management Science (2003- ), Discrete Optimization (2003-), and Constraints (1995-).

Guest Editor (with Yves Crama, Pierre Hansen, Frederic Maffray, Bruno Simeone and Dominique de Werra)

of the special volume of the Annals of Operations Research dedicated to the memory of Peter L. Hammer

(1936-2006).

 

Courses Taught

01:711:453  Theory of Linear Optimization
01:711:465  Integer Programming
16:711:513  Discrete Optimization
16:711:517  Computational Methods of Operations Research
16:711:553  Boolean Functions
16:711:611  Pseudo-Boolean Functions

Fall 2010: Discrete Optimization

 

 

Research Areas

Discrete Optimization, Integer Programming, Unconstrained Binary Optimization, and their applications

in VLSI design, etc.

Theory of Boolean Functions, Satisfiability, Dualization, and Horn functions.

Theory of Partially Defined Boolean Functions, and Machine Learning

Enumeration Methods, and their Applications in Data Mining, Reliability Theory, etc.

Graph Theory, Game Theory and Combinatorics

Publications    

Recent Publications in Refereed Journals:

Endre Boros, Vladimir A. Gurvich and Igor E. Zverovich: Friendship two-graphs. Graphs and Combinatorics 26, 617-628, 2010.   
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. In Integer Programming and Combinatorial Optimization, Proceedings of the 14th International Conference, IPCO 2010 (F. Eisenbrand and F.B. Shepherd, Eds) Lausanne, Switzerland, June 2010, LNCS 6080, 341-354, 2010.

Endre Boros, Khaled Elbassioni, Kazuhisa Makino: Left-to-right multiplication for monotone Boolean dualization. SIAM Journal on Computing 39 (7), 3424-3439, 2010.

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: On effectivity functions of game forms . Games and Economic Behavior 68, 512-531, 2010.

Paul Kantor and Endre Boros: Deceptive Detection Methods for Effective Security with Inadequate Budgets: The Testing Power. Risk Analysis 30 (4), 663-673, 2010.

Diogo V. Andrage, Endre Boros, Vladimir Gurvich: Not complementary connected and not CIS d-graphs form weakly monotone families. Discrete Mathematics 310 (5), 1089-1096, 2010.

Endre Boros, Vladimir Gurvich, Kazuhisa Makino and David Papp: Acyclic, or totally tight, two-person game forms; characterization and main properties. Discrete Mathematics 310 (6-7), 1135-1151, 2010.

Endre Boros, Ondrej Cepek, Alexander Kogan, Petr Kucera: Exclusive and essential sets of implicates of Boolean functions. Discrete Applied Mathematics 158 (2), 81-96, 2010.

Endre Boros, Ondrej Cepek, Alexander Kogan, Petr Kucera: A subclass of Horn CNFs optimally compressible in polynomial time. Annals of Mathematics and Artificial Intelligence 57 (3-4), 249-291, 2009.

E. Boros and K. Makino: A fast and simple parallel algorithm for the monotone duality problem. In ICALP 09: Proceedings of the 36th International Colloquium on Automata, languages and Programming, LNCS 5555 (2009).

E. Boros, V. Gurvich, and K. Makino: Minimal and locally minimal games and game forms. Discrete Mathematics 309 (13), 4456-4468, 2009.

Endre Boros and Vladimir Gurvich: Vertex- and edge-minimal and locally minimal graphs. Discrete Mathematics 309 (12), 3853-3865, 2009.

E. Boros, L. Fedzhora, P.B. Kantor, K. Saeger, P. Stroud:  Large scale LP model for finding optimal container inspection strategies. Naval Research Logistics, Vol. 56 (5), 404-420, 2009.

T. Unluyurt and E. Boros: A note on optimal resource allocation for security in reliability systems. European Journal of Operational Research 199, 601-603, 2009.

E. Boros, V. Gurvich and I. Zverovich: On split and almost CIS-graphs. Australasian Journal of Cmbinatorics 43, 163-180, 2009.

K. Borys, E. Boros, V. Gurvich and G. Rudolf: Generating 3-vertex connected spanning subgraphs.  Discrete Mathematics 308 (24), 6285-6297, 2008.

Endre Boros, Peter L. Hammer, Richard Sun and Gabriel Tavares. A max-flow approach to improved lower bounds for quadratic 0-1 minimization.  Discrete Optimization 5 (2), 501-529, 2008.

L. Khachiyan, E. Boros, K. Elbassioni and V. 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.

E. Boros, L. Lei, Y. Zhao and H. Zhong: Scheduling vessels and container-yard operations with conflicting objectives. Annals of Operations Research 161, 149-170, 2008.

E. Boros, L. Khachiyan, K. Borys, K. Elbassioni, V. Gurvich and K. Makino: Enumerating cut conjunctions in graphs and related problems. Algorithmica 51 (3), 239-263, 2008.

E. Boros, E. Elsayed, P. Kantor, M. Xie and F.S. Roberts: Optimization problems for port-of-entry detection systems. In:Intelligence and Security Informatics: Techniques and Applications. H. Chen and C.C. Yang (eds.), 319-335, Springer, 2008.

Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Kazuhisa Makino: Generating vertices of polyhedra and related problems of monotone generation. Centre de Recherches Matematiques CRM Proceedings and Lecture Notes 48, 2008.

E. Boros, K. Elbassioni and K. Makino: On Berge Multiplication for Monotone Boolean Dualization. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykhavik, Iceland, July 2008, volume 5125 of Lecture Notes in Computer Science, 48-59, Springer Verlag, 2008.

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 of Computing Systems 43 (2), 204-233, 2008.

Endre Boros, Vladimir Gurvich and Igor Zverovich: Neighborhood hypergraphs of bipartite graphs.  Journal of Graph Theory 58 (1), 69-95, 2008.

Boros, E., Elbassioni, K., Gurvich, V. & Khachiyan, L.: On Enumerating Minimal Dicuts and Strongly Connected Subgraphs.  Algorithmica  50, 159-172, 2008.

K. Haraguchi, M. Yagiura, E. Boros and T. Ibaraki: A Randomness Based Analysis on the Data Size Needed for Removing Deceptive Patterns.  IEICE Transactions on Information and Systems, E91-D (2008) 781-788.

E. Boros, R. Brualdi, Y. Crama, and A.J. Hoffman:  Gersgorin variations III: On a theme of Brualdi and Varga. Linear Algebra and Its Applications 428, 14-19, 2008.

Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich. Generating all vertices of a polyhedron is hard. Discrete and Computational Geometry, 174-190, 2008.

E. Boros, P.L. Hammer and G. Tavares.  Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO).  J. Heuristics 13, 2007, pp. 99-132.

L.Khachiyan, E. Boros, K. Elbassioni, V. Gurvich and K. Makino.  Enumerating disjunctions and conjunctions of paths and cuts in reliability theory.  Discrete Applied Mathematics 155 (2), 2007, pp. 137-149.

L. Khachiyan, E. Boros, V. Gurvich and K. Elbassioni.  Computing many maximal independent sets for hypergraphs in parallel.  Parallel Processing Letters 2, 2007, pp. 141-152.

L.Khachiyan, E.Boros, K. Elbassioni, and V.Gurvich:  A global parallel algorithm for the hypergraph transversal problem.  Information Processing Letters 101 (4), 2007, 148-155.

L. Khachiyan, E.Boros, K. Elbassioni, V.Gurvich, and K. Makino:  Dual-bounded generating problems:

efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data.  Theoretical Computer Science 379 (Special issue, ed. G. Woeginger), 2007, pp 361-376.

L.Khachiyan, E.Boros, K. Elbassioni, and V.Gurvich:  On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs.  Theoretical Computer Science 382, 2007, pp 139-150.

L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, and K. Makino: Enumerating spanning and connected subsets in graphs and matroids.  JORSJ (Journal of the Operations Research Society of Japan) 50 (4), 325-338, 2007.

Publications Accepted in Refereed Journals:

E. Boros, K. Elbassioni, V. Gurvich, H.R.Tiwary:The negative cycles polyhedron and hardness of checking some polyhedral properties (to appear in Annals of Operations Research Special Volume in honor of P.L. Hammer).

Endre Boros, Vladimir A. Gurvich and Igor E. Zverovich: Friendship two-graphs. RRR 7-2008 (to appear in Graphs and Combinatorics).

 

Recent RUTCOR Research Reports:

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: A potential reduction algorithm for ergodic mean payoff stochastic games with perfect information. RRR 5-2010.

Endre Boros, Ondrej Cepek, Vladimir Gurvich, Kazuhisa Makino, Igor E. Zverovich: Separable discrete functions. RRR 26-2009.

Endre Boros, Robert Rand: Terminal games with 3 terminals have proper Nash equilibria in pure positional strategies. RRR 22-2009.

Endre Boros, Vladimir Gurvich: Why chess and backgammon can be solved in pure positional uniformly optimal stretegies. RRR 21-2009.

Endre Boros, Vladimir Gurvich, Kazuhisa Makino, Wei Shao: Nash solvable bidirected cyclic two-person game forms. RRR 20-2009.

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. RRR 19-2009.

Endre Boros, Vladimir Gurvich, Khaled Elbassioni, and Kazuhisa Makino: Every Stochastic Game with Perfect Information Admits a Canonical Form. RRR 9-2009.

Endre Boros, Vladimir Gurvich, and Matthew Oster: More Extremal Properties of de Bruijn Sequences. RRR 8-2009.

Endre Boros, Yves Crama, Peter L. Hammer, Toshihide Ibaraki, Alexander Kogan, Kazuhisa Makino: Logical Analysis of Data: Classification with Justification. RRR 5-2009.

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: On effectivity functions of game forms . RRR 3-2009.

Endre Boros, Vladimir A. Gurvich, Igor E. Zverovich, and Wei Shao: Assignability of 3-dimensional totally tight matrices. RRR 2-2009.

Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Hans Raj Tiwary: The Negative Cycles Polyhedron and Hardness of Checking Some Polyhedral Properties. RRR 5-2008.

E. Boros, K. Elbassioni, V. Gurvich, K. Makino, and V. Oudalov: Computer-generated theorems on Nash solvability of bimatrix games based on excluding certain $2 \times 2$  subgames.  RRR 31-2007. 

Endre Boros and Vladimir Gurvich: On complexity of algorithms for modeling disease transmission and optimal vaccination strategy. RRR 16-2007.

Diogo V. Andrade, Endre Boros and Vladimir Gurvich: On graphs whose maximal cliques and stable sets intersect. RRR 17-2006.

Endre Boros, Peter L. Hammer and Gabriel Tavares: Preprocessing of Unconstrained Quadratic Binary Optimization.  RRR 10-2006.

E. Boros and L. Everett: Linear Programming Approach for Optimal Protein Encoding. RRR 14-2005.

Diogo Andrade, Endre Boros and Vladimir Gurvich. Even-hole-free and Balanced Circulants. RRR 8-2005.

 

Books, Chapters and Edited Volumes:

E. Boros, T. Ibaraki, & K. Makino, Partially Defined Boolean Functions, Cambridge University Press, forthcoming, 2009.

E. Boros, Horn Functions, In: Boolean Functions (Y. Crama and P.L. Hammer, eds.) Cambridge University Press, forthcoming, 2009.

D. deWerra, E. Boros, A. Hertz, M. Widmer, J. Carlier, editors. In Fifth International Conference on Graphs and Optimization 2006, volume 156 (13) of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, July 2008. Elsevier Science, pp. 2437-2580.

E. Boros and V. Gurvich, editors. In Memory of Leonid Khachiyan (1952 - 2005), volume 156 (11) of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, June 2008. Elsevier Science, pp. 1957-2240.

M. Anthony, E. Boros, P.L. Hammer, and A. Kogan, editors. Discrete Mathematics and Data Mining II, volume 156 (6) of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, March 2008. Elsevier Science, pp. 823-984.

M. Anthony, E. Boros, P.L. Hammer, and A. Kogan, editors. Discrete Mathematics and Data Mining II, volume 154 (7) of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford,Shannon, Singapore, Tokyo, May 2006. Elsevier Science, pp. 1037-1156.

E. Boros, P.L. Hammer, & T. Ibaraki, Logical Analysis of Data. In: Encyclopedia of Data Warehousing and Mining, (J. Wang, ed.) Idea Group Reference, (2005), pp. 689-692.

M. Anthony, E. Boros, P.L. Hammer, and A. Kogan, editors. Discrete Mathematics and Data Mining, volume 144 (1-2) of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, September 2004. Elsevier Science, pp. 1-228.

E. Boros and P.L. Hammer, editors. Workshop on Discrete Optimization DO'99: Contributions to Discrete Optimization, volume 124 of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, December 2002. Elsevier Science, pp. 1-142.

E. Boros and P.L. Hammer, editors.Workshop on Discrete Optimization DO'99: Surveys on the State of the Art, volume 123 of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, November 2002. Elsevier Science, pp. 1-580.

E. Boros, John Franco, Eugine Freuder, Martin C. Golumbic, R. Greiner, and E. Mayoraz, editors. Artificial Intelligence and Mathematics IX., volume 26 of Annals of Mathematics and Artificial Intelligence. December 1999, Baltzer Science Publishers, pp. 1-257.

J.V. Franco, G. Gallo, H.K. Buning, E. Speckenmeyer, E. Boros, and P.L. Hammer, editors. The Satisfiability Problem/Boolean Functions, volume 96-97 of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, November 1999. Elsevier Science, pp. 1-482.

E. Boros and P.L. Hammer, editors. Boolean Functions, volume 10 of Topics in Discrete Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, December 1999. Elsevier Science, pp. 1-482.

E. Boros, J. Franco, E. Freuder, M.C. Golumbic, R. Greiner, and E. Mayoraz, editors. Artificial Intelligence and Mathematics VIII., volume 24 of Annals of Mathematics and Artificial Intelligence, December 1998, Baltzer Science Publishers, pp. 1-250.

E. Boros and R. Greiner, editors. Artificial Intelligence and Mathematics, December 1997. Electronic Proceedings of the Fifth International Symposiums on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, January 4-6, 1998.

E. Boros and M.C. Golumbic, editors. Artificial Intelligence and Mathematics V., volume 17 of Annals of Mathematics and Artificial Intelligence. December 1996, Baltzer Science Publishers, pp. 1-176.

E. Boros, editor. ARIDAM VI and VII, volume 60 of Discrete Applied Mathematics. June 1995, Elsevier Science, pp. 1-390.

 

Courses

Research

Publications