Zbigniew Lonc
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Zbigniew Lonc has a total of 34 co-authors. Here are the top co-authors by number of shared publications:
- Michał Dębski
Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland
8 shared publications - Miroslaw Truszczynski
University of Kentucky
7 shared publications Mirosław Truszczyński
Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA
7 shared publications- Paweł Rzążewski
Warsaw University of Technology Warsaw Poland
7 shared publications - Konstanty Junosza-Szaniawski
Warsaw University of Technology Warsaw Poland
3 shared publications Krzysztof Bryś
Faculty of Mathematics and Information Science, Warsaw University of Technology, Pl. Politechniki 1, 00-661 Warsaw, Poland
3 shared publications
Latest Publications
- 28 February 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs
We study the problem of fair allocation of indivisible goods that form a graph and the bundles that are distributed to agents are connected subgraphs of this graph. We focus on the proportional and the maximin share fairness criteria. It is well-known that allocations satisfying these criteria may not exist for many graphs including complete graphs and cycles. Therefore, it is natural to look for approximate allocations, i.e., allocations guaranteeing each agent a certain portion of the value that is satisfactory to her. In this paper we consider the class of graphs of goods which do not contain a star with d+1 edges (where d > 1) as an induced subgraph. This is a large class of graphs containing graphs with the maximum degree bounded by d. For this class of graphs we show a theorem which specifies what fraction of the proportional share can be guaranteed to each of n agents if the values of single goods for the agents are bounded by a given fraction of this share. Furthermore, an allocation ensuring such a guarantee can be computed in polynomial time. This theorem can be viewed as analogous to a result by Hill in1987, who solved a similar problem for proportional allocations without connectivity constraints. Moreover, for the same class of graphs of goods, we prove that there is an allocation assigning each of n agents a connected bundle of value at least n/(d(n-1)+1) > 1/d of her maximin share, and this allocation can be computed in polynomial time.
- 28 February 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs
We study the problem of fair allocation of indivisible goods that form a graph and the bundles that are distributed to agents are connected subgraphs of this graph. We focus on the proportional and the maximin share fairness criteria. It is well-known that allocations satisfying these criteria may not exist for many graphs including complete graphs and cycles. Therefore, it is natural to look for approximate allocations, i.e., allocations guaranteeing each agent a certain portion of the value that is satisfactory to her. In this paper we consider the class of graphs of goods which do not contain a star with d+1 edges (where d > 1) as an induced subgraph. This is a large class of graphs containing graphs with the maximum degree bounded by d. For this class of graphs we show a theorem which specifies what fraction of the proportional share can be guaranteed to each of n agents if the values of single goods for the agents are bounded by a given fraction of this share. Furthermore, an allocation ensuring such a guarantee can be computed in polynomial time. This theorem can be viewed as analogous to a result by Hill in1987, who solved a similar problem for proportional allocations without connectivity constraints. Moreover, for the same class of graphs of goods, we prove that there is an allocation assigning each of n agents a connected bundle of value at least n/(d(n-1)+1) > 1/d of her maximin share, and this allocation can be computed in polynomial time.
- 29 June 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (12)
Edge decompositions and rooted packings of graphs
- 29 June 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (12)
Edge decompositions and rooted packings of graphs
- Open Access
Dilworth's Theorem for Borel Posets
A famous theorem of Dilworth asserts that any finite poset of width $k$ can be decomposed into $k$ chains. We study the following problem: given a Borel poset $P$ of finite width $k$, is it true that it can be decomposed into $k$ Borel chains? We give a positive answer in a special case of Borel posets embeddable into the real line. We also prove a dual theorem for posets whose comparability graphs are locally countable.Open AccessDilworth's Theorem for Borel Posets
A famous theorem of Dilworth asserts that any finite poset of width $k$ can be decomposed into $k$ chains. We study the following problem: given a Borel poset $P$ of finite width $k$, is it true that it can be decomposed into $k$ Borel chains? We give a positive answer in a special case of Borel posets embeddable into the real line. We also prove a dual theorem for posets whose comparability graphs are locally countable. - 1 April 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 277, 82-91
Bundling all shortest paths
- 1 April 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 277, 82-91
Bundling all shortest paths
- Open Access
Maximin share allocations on cycles
The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the case when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. For the maximin share fairness criterion researchers proved that if goods form a tree, allocations offering each agent a bundle of at least her maximin share value always exist. Moreover, they can be found in polynomial time. We consider here the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out to be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide results on allocations guaranteeing each agent a certain portion of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.
Open AccessMaximin share allocations on cycles
The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the case when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. For the maximin share fairness criterion researchers proved that if goods form a tree, allocations offering each agent a bundle of at least her maximin share value always exist. Moreover, they can be found in polynomial time. We consider here the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out to be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide results on allocations guaranteeing each agent a certain portion of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.
- 1 July 2018
- Published by International Joint Conferences on Artificial Intelligence
- p. 410-416
Maximin Share Allocations on Cycles
The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the setting when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. Researchers proved that, unlike in the original problem (which corresponds to the case of the complete graph in the extended setting), in the case of the goods-graph being a tree, allocations offering each agent a bundle of or exceeding her maximin share value always exist. Moreover, they can be found in polynomial time. We consider here the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide results on allocations guaranteeing each agent a certain portion of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.
- 1 July 2018
- Published by International Joint Conferences on Artificial Intelligence
- p. 410-416
Maximin Share Allocations on Cycles
The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the setting when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. Researchers proved that, unlike in the original problem (which corresponds to the case of the complete graph in the extended setting), in the case of the goods-graph being a tree, allocations offering each agent a bundle of or exceeding her maximin share value always exist. Moreover, they can be found in polynomial time. We consider here the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide results on allocations guaranteeing each agent a certain portion of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.
- 1 December 2017
- Published by Elsevier in European Journal of Combinatorics
- Vol. 66, 60-80
Harmonious and achromatic colorings of fragmentable hypergraphs
- 1 December 2017
- Published by Elsevier in European Journal of Combinatorics
- Vol. 66, 60-80
Harmonious and achromatic colorings of fragmentable hypergraphs
- Open Access
- 26 September 2017
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Discrete Mathematics & Theoretical Computer Science
- Vol. 19 no. 3 (Analysis o)
Tight Euler tours in uniform hypergraphs - computational aspects
By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed modulo $s$) and the sets $e_i$ for $i=0,\ldots,s-1$ are pairwise different. A tight tour in $H$ is a tight Euler tour if it contains all edges of $H$. We prove that the problem of deciding if a given $3$-uniform hypergraph has a tight Euler tour is NP-complete, and that it cannot be solved in time $2^{o(m)}$ (where $m$ is the number of edges in the input hypergraph), unless the ETH fails. We also present an exact exponential algorithm for the problem, whose time complexity matches this lower bound, and the space complexity is polynomial. In fact, this algorithm solves a more general problem of computing the number of tight Euler tours in a given uniform hypergraph.- 26 September 2017
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Discrete Mathematics & Theoretical Computer Science
- Vol. 19 no. 3 (Analysis o)
Open AccessTight Euler tours in uniform hypergraphs - computational aspects
By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed modulo $s$) and the sets $e_i$ for $i=0,\ldots,s-1$ are pairwise different. A tight tour in $H$ is a tight Euler tour if it contains all edges of $H$. We prove that the problem of deciding if a given $3$-uniform hypergraph has a tight Euler tour is NP-complete, and that it cannot be solved in time $2^{o(m)}$ (where $m$ is the number of edges in the input hypergraph), unless the ETH fails. We also present an exact exponential algorithm for the problem, whose time complexity matches this lower bound, and the space complexity is polynomial. In fact, this algorithm solves a more general problem of computing the number of tight Euler tours in a given uniform hypergraph. - 1 July 2017
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 225, 51-63
Sequences of radius for complete bipartite graphs- 1 July 2017
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 225, 51-63
Sequences of radius for complete bipartite graphs- 1 March 2017
- Published by Elsevier in Discrete Mathematics
- Vol. 340 (3) , 504-507
Note on a construction of short -radius sequences- 1 March 2017
- Published by Elsevier in Discrete Mathematics
- Vol. 340 (3) , 504-507
Note on a construction of short -radius sequences