Endre Boros

TCS Journal 2024 Journal Article

Envy-free relaxations for goods, chores, and mixed items

• Kristóf Bérczi
• Erika R. Bérczi-Kovács
• Endre Boros
• Fekadu Tolessa Gedefa
• Naoyuki Kamiyama
• Telikepalli Kavitha
• Yusuke Kobayashi
• Kazuhisa Makino

In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are { 0, + 1 } -valued functions, and negative Boolean utilities that are { 0, − 1 } -valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.

TCS Journal 2022 Journal Article

Unique key Horn functions

• Kristóf Bérczi
• Endre Boros
• Ondřej Čepek
• Petr Kučera
• Kazuhisa Makino

Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely defines a pure Horn function h, representing the functional dependencies. If the knowledge of the attribute values in set A determines the value for attribute v, then A → v is an implicate of h. If K is a key of the database, then K → v is an implicate of h for all attributes v. Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co- NP -complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay, improving on earlier results. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the Minimum Key problem is at least as hard as the Minimum Target Set Selection problem with bounded thresholds.

TCS Journal 2021 Journal Article

Generating clause sequences of a CNF formula

• Kristóf Bérczi
• Endre Boros
• Ondřej Čepek
• Khaled Elbassioni
• Petr Kučera
• Kazuhisa Makino

Given a CNF formula Φ with clauses C 1, …, C m and variables V = { x 1, …, x n }, a truth assignment a: V → { 0, 1 } of Φ leads to a clause sequence σ Φ ( a ) = ( C 1 ( a ), …, C m ( a ) ) ∈ { 0, 1 } m where C i ( a ) = 1 if clause C i evaluates to 1 under assignment a, otherwise C i ( a ) = 0. The set of all possible clause sequences carries a lot of information on the formula, e. g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties. We consider a problem posed at Dagstuhl Seminar 19211 “Enumeration in Data Management” (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay.

I&C Journal 2019 Journal Article

A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions

• Endre Boros
• Khaled Elbassioni
• Vladimir Gurvich
• Kazuhisa Makino

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = ( V, E ), with local rewards r: E → Z, and three types of positions: black V B, white V W, and random V R forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when | V R | = 0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, 1 we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with | V R | = O ( 1 ), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in | V W | + | V B |, the maximum absolute local reward, and the common denominator of the transition probabilities.

TCS Journal 2019 Journal Article

Sprague-Grundy function of matroids and related hypergraphs

• Endre Boros
• Vladimir Gurvich
• Nhan Bao Ho
• Kazuhisa Makino
• Peter Mursic

We consider a generalization of the classical game of Nim called hypergraph Nim. Given a hypergraph H on the ground set V = { 1, …, n } of n piles of stones, two players alternate in choosing a hyperedge H ∈ H and strictly decreasing all piles i ∈ H. The player who makes the last move is the winner. In this paper we give an explicit formula that describes the Sprague-Grundy function of hypergraph Nim for several classes of hypergraphs. In particular we characterize all 2-uniform hypergraphs (that is graphs) and all matroids for which the formula works. We show that all self-dual matroids are included in this class.

TCS Journal 2013 Journal Article

A decomposition method for CNF minimality proofs

• Endre Boros
• Ondřej Čepek
• Petr Kučera

A CNF is minimal if no shorter CNF representing the same function exists, where by CNF length we mean either the number of clauses or the total number of literals (sum of clause lengths). In this paper we develop a decomposition approach that can be in certain situations applied to a CNF formula when proving its minimality. We give two examples in which this decomposition approach is used. Both examples deal with pure Horn minimization, a problem defined as follows: given a pure Horn CNF, construct a logically equivalent pure Horn CNF which is the shortest possible (either w. r. t. the number of clauses or w. r. t. the total number of literals). Both presented examples give alternative proofs of known complexity results for pure Horn minimization.

TCS Journal 2007 Journal Article

Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data

• Leonid Khachiyan
• Endre Boros
• Khaled Elbassioni
• Vladimir Gurvich
• Kazuhisa Makino

We show that ∣ X ∣ ≤ n ∣ Y ∣ must hold for two finite sets X, Y ⊂ R n whenever they can be separated by a nonnegative linear function such that X is above Y and the componentwise minimum of any two distinct points in X is dominated by some point in Y. As a consequence, we obtain an incremental quasi-polynomial time algorithm for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p -inefficient points of a given discrete probability distribution, and for generating all maximal hyper-rectangles which contain a specified fraction of points of a given set in R n. This provides a substantial improvement over previously known exponential time algorithms for these generation problems related to Integer and Stochastic Programming, and Data Mining. Furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, implying that for discrete probability distributions with independent coordinates, both p -efficient and p -inefficient points can be separately generated in incremental polynomial time.

TCS Journal 2007 Journal Article

On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs

• Leonid Khachiyan
• Endre Boros
• Khaled Elbassioni
• Vladimir Gurvich

Given a finite set V, and integers k ≥ 1 and r ≥ 0, let us denote by A ( k, r ) the class of hypergraphs A ⊆ 2 V with ( k, r ) -bounded intersections, i. e. in which the intersection of any k distinct hyperedges has size at most r. We consider the problem MIS ( A, I ): given a hypergraph A, and a subfamily I ⊆ I ( A ) of its maximal independent sets (MIS) I ( A ), either extend this subfamily by constructing a new MIS I ∈ I ( A ) ∖ I or prove that there are no more MIS, that is I = I ( A ). It is known that, for hypergraphs of bounded dimension A ( 1, δ ), as well as for hypergraphs of bounded degree A ( δ, 0 ) (where δ is a constant), problem MIS ( A, I ) can be solved in incremental polynomial time. In this paper, we extend this result to any integers k, r such that k + r = δ is a constant. More precisely, we show that for hypergraphs A ∈ A ( k, r ) with k + r ≤ const, problem MIS ( A, I ) is NC-reducible to the problem MIS ( A ′, 0̸ ) of generating a single MIS for a partial subhypergraph A ′ of A. In particular, this implies that MIS ( A, I ) is polynomial, and we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximally independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A ( 1, δ ), A ( δ, 0 ), and A ( 2, 1 ), where δ is a constant. We also show that, for A ∈ A ( k, r ), where k + r ≤ const, the problem of generating all MIS of A can be solved in incremental polynomial-time and with space polynomial only in the size of A.

SODA Conference 2006 Conference Paper

Generating all vertices of a polyhedron is hard

• Leonid Khachiyan
• Endre Boros
• Konrad Borys
• Khaled M. Elbassioni
• Vladimir Gurvich

MFCS Conference 2005 Conference Paper

Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities

• Leonid Khachiyan
• Endre Boros
• Khaled M. Elbassioni
• Vladimir Gurvich

Abstract We consider monotone ∨, ∧-formulae φ of m atoms, each of which is a monotone inequality of the form f i ( x )≥ t i over the integers, where for i = 1, .. ., m, \(f_i: \mathbb{Z}^n \mapsto \mathbb{R}\) is a given monotone function and t i is a given threshold. We show that if the ∨-degree of φ is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying φ can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of m inequalities is NP-hard when m is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.

MFCS Conference 2004 Conference Paper

Generating Paths and Cuts in Multi-pole (Di)graphs

• Endre Boros
• Khaled M. Elbassioni
• Vladimir Gurvich
• Leonid Khachiyan
• Kazuhisa Makino

Abstract Let G =( V, E ) be a (directed) graph with vertex set V and edge (arc) set E. Given a set \(\mathcal P\) of (source-sink) pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of \(\mathcal P\). For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. For directed graphs both of these problems are NP-hard. We also give a polynomial delay algorithm for enumerating minimal sets of arcs connecting respectively two given nodes s 1 and s 2 to a given vertex t 1, and each vertex of a given subset of vertices T 2.

I&C Journal 2003 Journal Article

Variations on extending partially defined Boolean functions with missing bits

• Endre Boros
• Toshihide Ibaraki
• Kazuhisa Makino

In this paper we consider four possible definitions for extending a partially defined Boolean function in which the input contains some missing bits. We show somewhat surprisingly that, for many general and frequently used families of function classes, three of these notions of an extension are mathematically equivalent, though such an equivalence does not hold universally, as demonstrated by several examples.

MFCS Conference 2002 Conference Paper

Matroid Intersections, Polymatroid Inequalities, and Related Problems

• Endre Boros
• Khaled M. Elbassioni
• Vladimir Gurvich
• Leonid Khachiyan

Abstract Given m matroids M 1, .. ., M m on the common ground set V, it is shown that all maximal subsets of V, independent in the m matroids, can be generated in quasi-polynomial time. More generally, given a system of polymatroid inequalities f 1 ( X ) ≥ t 1, .. ., f m ( X ) ≥ t m with quasi-polynomially bounded right hand sides t 1, .. ., tm, all minimal feasible solutions X ⊆ V to the system can be generated in incremental quasi-polynomial time. Our proof of these results is based on a combinatorial inequality for polymatroid functions which may be of independent interest. Precisely, for a polymatroid function f and an integer threshold t ≥ 1, let α = α( f, t ) denote the number of maximal sets X ⊆ V satisfying f ( X ) < t, let β = β( f t ) be the number of minimal sets X ⊆ V for which f ( X ) ≥ t, and let n = | V |. We show that α ≤ max n, β(log t )/ c, where c = c ( n, β) is the unique positive root of the equation 2 c ( n c /logβ - 1) = 1. In particular, our bound implies that α ≤ ( n β) log t. We also give examples of polymatroid functions with arbitrarily large t n, α and β for which α = β( 1 - 0 1))log t/c.

AIJ Journal 1999 Journal Article

Logical analysis of binary data with missing bits

• Endre Boros
• Toshihide Ibaraki
• Kazuhisa Makino

We model a given pair of sets of positive and negative examples, each of which may contain missing components, as a partially defined Boolean function with missing bits (pBmb) (T~, F~), where T~-⊂{0, 1*} n and F~-⊂{0, 1*} n, and “*” stands for a missing bit. Then we consider the problem of establishing a Boolean function (an extension) f: 0, 1 n → 0, 1 belonging to a given function class C, such that f is true (respectively, false) for every vector in T~ (respectively, in F~. This is a fundamental problem, encountered in many areas such as learning theory, pattern recognition, example-based knowledge bases, logical analysis of data, knowledge discovery and data mining. In this paper, depending upon how to deal with missing bits, we formulate three types of extensions called robust, consistent and most robust extensions, for various classes of Boolean functions such as general, positive, Horn, threshold, decomposable and k-DNF. The complexity of the associated problems are then clarified; some of them are solvable in polynomial time while the others are NP-hard.

I&C Journal 1998 Journal Article

Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions

• Endre Boros
• Toshihide Ibaraki
• Kazuhisa Makino

In this paper, we address a fundamental problem related to the induction of Boolean logic: Given a set of data, represented as a set of binary “truen-vectors” (or “positive examples”) and a set of “falsen-vectors” (or “negative examples”), we establish a Boolean function (or an extension)f, so thatfis true (resp. , false) in every given true (resp. , false) vector. We shall further require that such an extension belongs to a certain specified class of functions, e. g. , class of positive functions, class of Horn functions, and so on. The class of functions represents our a priori knowledge or hypothesis about the extensionf, which may be obtained from experience or from the analysis of mechanisms that may or may not cause the phenomena under consideration. The real-world data may contain errors, e. g. , measurement and classification errors might come in when obtaining data, or there may be some other influential factors not represented as variables in the vectors. In such situations, we have to give up the goal of establishing an extension that is perfectly consistent with the given data, and we are satisfied with an extensionfhaving the minimum number of misclassifications. Both problems, i. e. , the problem of finding an extension within a specified class of Boolean functions and the problem of finding a minimum error extension in that class, will be extensively studied in this paper. For certain classes we shall provide polynomial algorithms, and for other cases we prove their NP-hardness.