4 papers
A Simplified Analysis of the Good-Bad -Approximation Algorithm for Some Minimum-Cost Graph Problems
Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade
In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected…
Approval-Based Apportionment: Like Portioning, Approximately like Committee Voting
Paul Gölz, Hannane Yaghoubizade
We study approval-based apportionment, a variant of committee elections in which candidates ("parties") can be selected several times. We show that the proportionality axioms EJR,…
Fair Division Among Couples and Small Groups
Paul Gölz, Hannane Yaghoubizade
We study the fair allocation of indivisible goods across groups of agents, where each agent fully enjoys all goods allocated to their group. We focus on groups of two (couples) and…
Partial Vertex Cover on Graphs of Bounded Degeneracy
Fahad Panolan, Hannane Yaghoubizade
In the Partial Vertex Cover (PVC) problem, we are given an -vertex graph and a positive integer , and the objective is to find a vertex subset of size maximizing…