Publications

Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, Roy Schwartz
Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification [pdf]
Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP’17)

Moses Charikar, Neha Gupta, Roy Schwartz
Local Guarantees in Graph Cuts and Clustering [pdf]
Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO’17)

Niv Buchbinder, Roy Schwartz, Baruch Weizman
Simplex Transformations and the Multiway Cut Problem [pdf]
Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17)

Niv Buchbinder, Moran Feldman, Roy Schwartz
Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization [pdf]
Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15)
Mathematics of Operations Research, Articles in Advance, 1-22, 2016

Niv Buchbinder, Moran Feldman, Roy Schwartz
Online Submodular Maximization with Preemption [pdf]
Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15)

Nicholas J. A. Harvey, Roy Schwartz, Mohit Singh
Discrepancy Without Partial Colorings [pdf]
Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’14)

Srikanth Kandula, Ishai Menache, Roy Schwartz, Spandana R. Babbula
Calendaring for Wide Area Networks [pdf]
Proceedings of the ACM Annual Conference of the Special Interest Group on Data Communication (SIGCOMM’14)
ACM SIGCOMM Computer Communication Review, 44(4), 515-526, 2014

Robert Krauthgamer, Joseph (Seffi) Naor, Roy Schwartz, Kunal Talwar
Non-Uniform Graph Partitioning [pdf]
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14)

Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz
Submodular Maximization with Cardinality Constraints [pdf]
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14)

Nikhil R. Devanur, Shaddin Dughmi, Roy Schwartz, Ankit Sharma, Mohit Singh
On the Approximation of Submodular Functions [pdf]
Arxiv 2013

Niv Buchbinder, Joseph (Seffi) Naor, Roy Schwartz
Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem [pdf]
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC’13)

Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai, Tami Tamir
All-or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns [pdf]
Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO’13)
ACM Transactions on Algorithms (TALG), 12(3), 2016

Ravi Kumar, Ronny Lempel, Roy Schwartz, Sergei Vassilvitskii
Rank Quantization [pdf]
Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM’13)

Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization [pdf]
Proceedings of the 53rd Annual IEEE Symposium on Foundations on Computer Science (FOCS’12)
SIAM J. Comput. (SICOMP), 44(5), 1384-1402, 2015 (invited to FOCS’12 special issue)
Winner of the 2017 SIAM Outstanding Paper Prize

Zohar S. Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein
Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem [pdf]
Proceedings of the 25th Conference on Learning Theory (COLT’12)
Journal of Machine Learning Research (JMLR), 23, 1-17, 2012

Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz
A Unified Continuous Greedy Algorithm for Submodular Maximization [pdf]
Proceedings of the 52nd Annual IEEE Symposium on Foundations on Computer Science (FOCS’11)

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, Roy Schwartz
Min-Max Graph Partitioning and Small Set Expansion [pdf]
Proceedings of the 52nd Annual IEEE Symposium on Foundations on Computer Science (FOCS’11)
SIAM J. Comput. (SICOMP), 43(2), 872-904, 2014 (invited to FOCS’11 special issue)

Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz, Justin Ward
Improved Approximations for k-Exchange Systems [pdf]
Proceedings of the 19th Annual European Symposium on Algorithms (ESA’11)

Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz
Improved Competitive Ratios for Submodular Secretary Problems [pdf]
Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’11)

Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm [pdf]
Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP’11)

Robert Krauthgamer, Joseph (Seffi) Naor, Roy Schwartz
Partitioning Graphs into Balanced Components [pdf]
Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09)

Rajsekar Manokaran, Joseph (Seffi) Naor, Prasad Raghavendra, Roy Schwartz
SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension, and Metric Labeling [pdf]
Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08)

Joseph (Seffi) Naor, Roy Schwartz
Balanced Metric Labeling [pdf]
Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC’05)

Joseph (Seffi) Naor, Roy Schwartz
Improved Competitive Ratios for Submodular Secretary Problems [pdf]
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’04)
ACM Transactions on Algorithms (TALG), 6(3), 2010