3 papers
cs.CC2026
An approximation notion between P and FPTAS
Samuel Bismuth, Erel Segal-Halevi
We present an approximation notion for NP-hard optimization problems. The notion is based on an amortized relaxation: the relaxed optimum of an input is the largest per-copy value…
cs.GT2025
Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations
Samuel Bismuth, Ivan Bliznets, Erel Segal-Halevi
A set of objects is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If we consider the objects as indivisible, many instances of the…
cs.DS2025
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…