23 citations · 47 across the 13 of their papers we have counts for
15 papers
A Tight Competitive Ratio for Online Submodular Welfare Maximization
Amit Ganz, Pranav Nuti, Roy Schwartz
In this paper we consider the online Submodular Welfare (SW) problem. In this problem we are given bidders each equipped with a general (not necessarily monotone) submodular ut…
Graph Balancing with Orientation Costs
Roy Schwartz, Ran Yeheskel
Motivated by the classic Generalized Assignment Problem, we consider the Graph Balancing problem in the presence of orientation costs: given an undirected multi-graph G = (V,E) equ…
Fault Tolerant Max-Cut
Keren Censor-Hillel, Noa Marelly, Roy Schwartz +1
In this work, we initiate the study of fault tolerant Max Cut, where given an edge-weighted undirected graph , the goal is to find a cut that maximizes the…
The Metric Relaxation for -Extension Admits an Gap
Roy Schwartz, Nitzan Tur
We consider the -Extension problem, where we are given an undirected graph equipped with non-negative edge weights , a collectio…
A Refined Analysis of Submodular Greedy
Ariel Kulik, Roy Schwartz, Hadas Shachnai
Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this gre…
Min-Max Correlation Clustering via MultiCut
Saba Ahmadi, Sainyam Galhotra, Samir Khuller +2
Correlation clustering is a fundamental combinatorial optimization problem arising in many contexts and applications that has been the subject of dozens of papers in the literature…