34 citations · 429 across the 66 of their papers we have counts for
9 papers · 1 filter
On Connected Strongly-Proportional Cake-Cutting
Zsuzsanna Jankó, Attila Joó, Erel Segal-Halevi +1
We investigate the problem of fairly dividing a divisible heterogeneous resource, also known as a cake, among a set of agents who may have different entitlements. We characterize t…
-times bin packing and its application to fair electricity distribution
Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi
Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does…
Computing approximate roots of monotone functions
Alexandros Hollender, Chester Lawrence, Erel Segal-Halevi
Given a function f: [a,b] -> R, if f(a) < 0 and f(b)> 0 and f is continuous, the Intermediate Value Theorem implies that f has a root in [a,b]. Moreover, given a value-oracle for f…
Efficient Almost-Egalitarian Allocation of Goods and Bads
Israel Jacobovich, Erel Segal-Halevi
We consider the allocation of indivisible objects among agents with different valuations, which can be positive or negative. An egalitarian allocation is an allocation that maximiz…
Coordinating Charitable Donations with Leontief Preferences
Felix Brandt, Matthias Greger, Erel Segal-Halevi +1
We consider the problem of funding public goods that are complementary in nature. Examples include charities handling different needs (e.g., protecting animals vs. providing health…
On Maximum Bipartite Matching with Separation
Pasin Manurangsi, Erel Segal-Halevi, Warut Suksompong
Maximum bipartite matching is a fundamental algorithmic problem which can be solved in polynomial time. We consider a natural variant in which there is a separation constraint: the…
Leximin Approximation: From Single-Objective to Multi-Objective
Eden Hartman, Avinatan Hassidim, Yonatan Aumann +1
Leximin is a common approach to multi-objective optimization, frequently employed in fair division applications. In leximin optimization, one first aims to maximize the smallest ob…
A Reduction from Chores Allocation to Job Scheduling
Xin Huang, Erel Segal-Halevi
We consider allocating indivisible chores among agents with different cost functions, such that all agents receive a cost of at most a constant factor times their maximin share. Th…
Cutting a Cake Fairly for Groups Revisited
Erel Segal-Halevi, Warut Suksompong
Cake cutting is a classic fair division problem, with the cake serving as a metaphor for a heterogeneous divisible resource. Recently, it was shown that for any number of players w…