10 citations · 19 across the 5 of their papers we have counts for
9 papers · 1 filter
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…
Online and Offline Greedy Algorithms for Routing with Switching Costs
Roy Schwartz, Mohit Singh, Sina Yazdanbod
Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between…