5 papers
Polynomial Binary Optimization
Endre Boros
In a binary polynomial optimization problem (BPO, in short) we are maximizing a multilinear polynomial expression depending on n binary variables. This is a hard optimization class…
Conformality of Minimal Transversals of Maximal Cliques
Endre Boros, Vladimir Gurvich, Martin MilaniÄ +2
Given a hypergraph , the dual hypergraph of is the hypergraph of all minimal transversals of . A hypergraph is conformal if it is the family of maximal cliques of a graph…
Two-person Positive Shortest Path Games Have Nash Equilibria in Pure Stationary Strategies
Endre Boros, Khaled Elbassioni, Vladimir Gurvich +1
We prove that every finite two-person shortest path game, where the local cost of every move is positive for each player, has a Nash equilibrium (NE) in pure stationary strategies,…
On Nash Equilibria in Play-Once and Terminal Deterministic Graphical Games
Endre Boros, Vladimir Gurvich, Kazuhisa Makino
We consider finite -person deterministic graphical games and study the existence of pure stationary Nash-equilibrium in such games. We assume that all infinite plays are equival…
Boole's probability bounding problem, linear programming aggregations, and nonnegative quadratic pseudo-Boolean functions
Endre Boros, Joonhee Lee
Hailperin (1965) introduced a linear programming formulation to a difficult family of problems, originally proposed by Boole (1854,1868). Hailperin's model is computationally still…