34 citations · 429 across the 66 of their papers we have counts for
8 papers · 1 filter
Time and Supply Fairness in Electricity Distribution using -times bin packing
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 the minimum number of bins such that the sum of the item sizes in each…
The Min Max Average Cycle Weight Problem
Noga Klein Elmalem, Rica Gonen, Erel Segal-Halevi
When an old apartment building is demolished and rebuilt, how can we fairly redistribute the new apartments to minimize envy among residents? We reduce this question to a combinato…
-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…
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…
Asymmetric Number Partitioning with Splitting and Interval Targets
Samuel Bismuth, Erel Segal-Halevi, Dana Shapira
The n-way number partitioning problem, a fundamental challenge in combinatorial optimization, has significant implications for applications such as fair division and machine schedu…
On Monotonicity of Number-Partitioning Algorithms
Erel Segal-Halevi
An algorithm for number-partitioning is called value-monotone if whenever one of the input numbers increases, the objective function (the largest sum or the smallest sum of a subse…
Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division
Elad Aigner-Horev, Erel Segal-Halevi
A matching in a bipartite graph with parts X and Y is called envy-free if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but…
Waste Makes Haste: Bounded Time Protocols for Envy-Free Cake Cutting with Free Disposal
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann
We consider the classic problem of envy-free division of a heterogeneous good ("cake") among several agents. It is known that, when the allotted pieces must be connected, the probl…