18 citations · 27 across the 25 of their papers we have counts for
32 papers
Approximating Submodular Matroid-Constrained Partitioning
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
The submodular partitioning problem asks to minimize, over all partitions of a ground set , the sum of a given submodular function over the parts of . The problem has…
Cyclic ordering of split matroids
Kristóf Bérczi, Áron Jánosik, Bence Mátravölgyi
There is a long list of open questions rooted in the same underlying problem: understanding the structure of bases or common bases of matroids. These conjectures suggest that matro…
On the Complexity of Inverse Bivariate Multi-unit Assignment Valuation Problems
Kristóf Bérczi, Lydia Mirabel Mendoza-Cadena
Inverse and bilevel optimization problems play a central role in both theory and applications. These two classes are known to be closely related due to the pioneering work of Dempe…
Reconfiguration of basis pairs in regular matroids
Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz
In recent years, combinatorial reconfiguration problems have attracted great attention due to their connection to various topics such as optimization, counting, enumeration, or sam…
Newton-type algorithms for inverse optimization II: weighted span objective
Kristóf Bérczi, Lydia Mirabel Mendoza-Cadena, Kitti Varga
In inverse optimization problems, the goal is to modify the costs in an underlying optimization problem in such a way that a given solution becomes optimal, while the difference be…
Newton-type algorithms for inverse optimization I: weighted bottleneck Hamming distance and -norm objectives
Kristóf Bérczi, Lydia Mirabel Mendoza-Cadena, Kitti Varga
In minimum-cost inverse optimization problems, we are given a feasible solution to an underlying optimization problem together with a linear cost function, and the goal is to modif…
Hypergraph Horn functions
Kristóf Bérczi, Endre Boros, Kazuhisa Makino
Horn functions form a subclass of Boolean functions possessing interesting structural and computational properties. These functions play a fundamental role in algebra, artificial i…
Weighted exchange distance of basis pairs
Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz
Two pairs of disjoint bases and of a matroid are called equivalent if can be transformed into by…
Matroid Intersection under Restricted Oracles
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds' fundamental theorem provides…
Exchange distance of basis pairs in split matroids
Kristóf Bérczi, Tamás Schwarcz
The basis exchange axiom has been a driving force in the development of matroid theory. However, the axiom gives only a local characterization of the relation of bases, which is a…
Inverse optimization problems with multiple weight functions
Kristóf Bérczi, Lydia Mirabel Mendoza-Cadena, Kitti Varga
We introduce a new class of inverse optimization problems in which an input solution is given together with linear weight functions, and the goal is to modify the weights by th…
A dual approach for dynamic pricing in multi-demand markets
Kristóf Bérczi, Erika R. Bérczi-Kovács, Evelin Szögi
Dynamic pricing schemes were introduced as an alternative to posted-price mechanisms. In contrast to static models, the dynamic setting allows to update the prices between buyer-ar…
Rainbow and monochromatic circuits and cuts in binary matroids
Kristóf Bérczi, Tamás Schwarcz
Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if a bina…
A 3/2-Approximation for the Metric Many-visits Path TSP
Kristóf Bérczi, Matthias Mnich, Roland Vincze
In the Many-visits Path TSP, we are given a set of cities along with their pairwise distances (or cost) , and moreover each city comes with an associated positive in…
Market Pricing for Matroid Rank Valuations
Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi
In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable to achieve o…
Envy-free Relaxations for Goods, Chores, and Mixed Items
Kristóf Bérczi, Erika R. Bérczi-Kovács, Endre Boros +5
In fair division problems, we are given a set of items and a set of agents with individual preferences, and the goal is to find an allocation of items among agents…
Unique key Horn functions
Kristóf Bérczi, Endre Boros, Ondřej Čepek +2
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 def…
Generating clause sequences of a CNF formula
Kristóf Bérczi, Endre Boros, Ondřej Čepek +3
Given a CNF formula with clauses and variables , a truth assignment of leads to a clause sequence $σ_Φ(a)=(C_…
Degree-Bounded Generalized Polymatroids and Approximating the Metric Many-Visits TSP
Kristóf Bérczi, André Berger, Matthias Mnich +1
In the Bounded Degree Matroid Basis Problem, we are given a matroid and a hypergraph on the same ground set, together with costs for the elements of that set as well as lower and u…
Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times
Kristóf Bérczi, Tamás Király, Simon Omlor
The paper considers single-machine scheduling problems with a non-renewable resource. In this setting, we are given a set jobs, each of which is characterized by a processing time,…
List colouring of two matroids through reduction to partition matroids
Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi
In the list coloring problem for two matroids, we are given matroids and on the same ground set , and the goal is to determine the smal…
Complexity of packing common bases in matroids
Kristóf Bérczi, Tamás Schwarcz
One of the most intriguing unsolved questions of matroid optimization is the characterization of the existence of disjoint common bases of two matroids. The significance of the…
Approximating minimum representations of key Horn functions
Kristóf Bérczi, Endre Boros, Ondřej Čepek +2
Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependenci…
Improving the Integrality Gap for Multiway Cut
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of terminal nodes, and the goal is to partition the node set of th…