Endre Boros
Director of RUTCOR Rutgers Center for Operations Research 640 Bartholomew Road Piscataway, NJ 088548003 Room 123 Tel: (732) 4453041 Fax: (732) 4455472 email: 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 01 Programming; advisor: Andras Prekopa Editorial ActivitiesEditorinChief 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 (19362006).
Courses Taught 01:711:453
Theory of Linear Optimization 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 PublicationsRecent Publications in Refereed Journals:Endre
Boros, Vladimir A. Gurvich and Igor E. Zverovich: Friendship twographs. Graphs and Combinatorics 26, 617628,
2010. Endre Boros, Khaled Elbassioni, Kazuhisa Makino: Lefttoright multiplication for monotone Boolean dualization. SIAM Journal on Computing 39 (7), 34243439, 2010. Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: On effectivity functions of game forms . Games and Economic Behavior 68, 512531, 2010. Paul Kantor and Endre Boros: Deceptive Detection Methods for Effective Security with Inadequate Budgets: The Testing Power. Risk Analysis 30 (4), 663673, 2010. Diogo V. Andrage, Endre Boros, Vladimir Gurvich: Not complementary connected and not CIS dgraphs form weakly monotone families. Discrete Mathematics 310 (5), 10891096, 2010. Endre Boros, Vladimir Gurvich, Kazuhisa Makino and David Papp: Acyclic, or totally tight, twoperson game forms; characterization and main properties. Discrete Mathematics 310 (67), 11351151, 2010. Endre Boros, Ondrej Cepek, Alexander Kogan, Petr Kucera: Exclusive and essential sets of implicates of Boolean functions. Discrete Applied Mathematics 158 (2), 8196, 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 (34), 249291, 2009. E. Boros and K. Makino: A fast and simple parallel algorithm for the monotone duality problem. In ICALP 09: Proceedings of the 36^{th} 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), 44564468, 2009. Endre Boros and Vladimir Gurvich: Vertex and edgeminimal and locally minimal graphs. Discrete Mathematics 309 (12), 38533865, 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), 404420, 2009. T. Unluyurt and E. Boros: A note on optimal resource allocation for security in reliability systems. European Journal of Operational Research 199, 601603, 2009. E. Boros, V. Gurvich and I. Zverovich: On split and almost CISgraphs. Australasian Journal of Cmbinatorics 43, 163180, 2009. K. Borys, E. Boros, V. Gurvich and G. Rudolf: Generating 3vertex connected spanning subgraphs. Discrete Mathematics 308 (24), 62856297, 2008. Endre Boros, Peter L. Hammer, Richard Sun and Gabriel Tavares. A maxflow approach to improved lower bounds for quadratic 01 minimization. Discrete Optimization 5 (2), 501529, 2008. L. Khachiyan, E. Boros, K. Elbassioni and V. Gurvich: Generating all minimal integral solutions to ANDOR systems of monotone inequalities: Conjunctions are simpler than disjunctions. Discrete Applied Mathematics 156 (11), 20202034, 2008. E. Boros, L. Lei, Y. Zhao and H. Zhong: Scheduling vessels and containeryard operations with conflicting objectives. Annals of Operations Research 161, 149170, 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), 239263, 2008. E. Boros, E. Elsayed, P. Kantor, M. Xie and F.S. Roberts: Optimization problems for portofentry detection systems. In:Intelligence and Security Informatics: Techniques and Applications. H. Chen and C.C. Yang (eds.), 319335, 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, 35^{th} International Colloquium, ICALP 2008, Reykhavik, Iceland, July 2008, volume 5125 of Lecture Notes in Computer Science, 4859, 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 nodewise limited interdiction. Theory of Computing Systems 43 (2), 204233, 2008. Endre Boros, Vladimir Gurvich and Igor Zverovich: Neighborhood hypergraphs of bipartite graphs. Journal of Graph Theory 58 (1), 6995, 2008. Boros, E., Elbassioni, K., Gurvich, V. & Khachiyan, L.: On Enumerating Minimal Dicuts and Strongly Connected Subgraphs. Algorithmica 50, 159172, 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, E91D (2008) 781788. 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, 1419, 2008. Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich. Generating all vertices of a polyhedron is hard. Discrete and Computational Geometry, 174190, 2008. E. Boros, P.L. Hammer and G. Tavares. Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO). J. Heuristics 13, 2007, pp. 99132. 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. 137149. L. Khachiyan, E. Boros, V. Gurvich and K. Elbassioni. Computing many maximal independent sets for hypergraphs in parallel. Parallel Processing Letters 2, 2007, pp. 141152. L.Khachiyan, E.Boros, K. Elbassioni, and V.Gurvich: A global parallel algorithm for the hypergraph transversal problem. Information Processing Letters 101 (4), 2007, 148155. L. Khachiyan, E.Boros, K. Elbassioni, V.Gurvich, and K. Makino: Dualbounded 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 361376. L.Khachiyan, E.Boros, K. Elbassioni, and V.Gurvich: On the dualization of hypergraphs with bounded edgeintersections and other related classes of hypergraphs. Theoretical Computer Science 382, 2007, pp 139150. 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), 325338, 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 twographs. RRR 72008 (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 52010. Endre Boros, Ondrej Cepek, Vladimir Gurvich, Kazuhisa Makino, Igor E. Zverovich: Separable discrete functions. RRR 262009. Endre Boros, Robert Rand: Terminal games with 3 terminals have proper Nash equilibria in pure positional strategies. RRR 222009. Endre Boros, Vladimir Gurvich: Why chess and backgammon can be solved in pure positional uniformly optimal stretegies. RRR 212009. Endre Boros, Vladimir Gurvich, Kazuhisa Makino, Wei Shao: Nash solvable bidirected cyclic twoperson game forms. RRR 202009. Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. RRR 192009. Endre Boros, Vladimir Gurvich, Khaled Elbassioni, and Kazuhisa Makino: Every Stochastic Game with Perfect Information Admits a Canonical Form. RRR 92009. Endre Boros, Vladimir Gurvich, and Matthew Oster: More Extremal Properties of de Bruijn Sequences. RRR 82009. Endre Boros, Yves Crama, Peter L. Hammer, Toshihide Ibaraki, Alexander Kogan, Kazuhisa Makino: Logical Analysis of Data: Classification with Justification. RRR 52009. Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino: On effectivity functions of game forms . RRR 32009. Endre Boros, Vladimir A. Gurvich, Igor E. Zverovich, and Wei Shao: Assignability of 3dimensional totally tight matrices. RRR 22009. Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Hans Raj Tiwary: The Negative Cycles Polyhedron and Hardness of Checking Some Polyhedral Properties. RRR 52008. E. Boros, K. Elbassioni, V. Gurvich, K. Makino, and V. Oudalov: Computergenerated theorems on Nash solvability of bimatrix games based on excluding certain $2 \times 2$ subgames. RRR 312007. Endre Boros and Vladimir Gurvich: On complexity of algorithms for modeling disease transmission and optimal vaccination strategy. RRR 162007. Diogo V. Andrade, Endre Boros and Vladimir Gurvich: On graphs whose maximal cliques and stable sets intersect. RRR 172006. Endre Boros, Peter L. Hammer and Gabriel Tavares: Preprocessing of Unconstrained Quadratic Binary Optimization. RRR 102006. E. Boros and L. Everett: Linear Programming Approach for Optimal Protein Encoding. RRR 142005. Diogo Andrade, Endre Boros and Vladimir Gurvich. Evenholefree and Balanced Circulants. RRR 82005.
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. 24372580. 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. 19572240. 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. 823984. 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. 10371156. 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. 689692. M. Anthony, E. Boros, P.L. Hammer, and A. Kogan, editors. Discrete Mathematics and Data Mining, volume 144 (12) of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, September 2004. Elsevier Science, pp. 1228. 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. 1142. 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. 1580. 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. 1257. J.V. Franco, G. Gallo, H.K. Buning, E. Speckenmeyer, E. Boros, and P.L. Hammer, editors. The Satisfiability Problem/Boolean Functions, volume 9697 of Discrete Applied Mathematics, Amsterdam, Lausanne, New York, Oxford, Shannon, Singapore, Tokyo, November 1999. Elsevier Science, pp. 1482. 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. 1482. 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. 1250. 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 46, 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. 1176. E. Boros, editor. ARIDAM VI and VII, volume 60 of Discrete Applied Mathematics. June 1995, Elsevier Science, pp. 1390.
