Niv Buchbinder


Survey book and Chapters

  • The Design of Competitive Online Algorithms via a Primal-Dual Approach. Niv Buchbinder and Joseph (Seffi) Naor. Foundations and Trends® in Theoretical Computer Science. [pdf]

  • Submodular Functions Maximization Problems. Niv Buchbinder and Moran Feldman. Chapter in the Second Edition of the "Handbook on Approximation Algorithms and Metaheuristics", Editor: Teofilo F. Gonzalez, Chapman & Hall/CRC, Taylor & Francis Group, 2016.

Conference Publications

  • The Online Set Cover Problem. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor, 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 100-105. [pdf]

  • Lower and Upper Bounds on Obtaining History Independence. Niv Buchbinder and Erez Petrank, 23rd Annual Int. Cryptography Conference (Crypto 2003), pp. 445-462. [pdf]

  • A General Approach to Online Network Optimization Problems. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor, ACM-SIAM Symposium on Discrete Algorithms (SODA 2004). [pdf]

  • Online Primal-Dual Algorithms for Covering and Packing Problems. Niv Buchbinder and Seffi Naor, 13th Annual European Symposium on Algorithms (ESA 2005) full version [pdf]

  • Fair Online Load Balancing. Niv Buchbinder and Seffi Naor, 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006) [pdf]

  • Improved Bounds for Online Routing and Packing via a Primal-Dual Approach. Niv Buchbinder and Seffi Naor, 47th annual ieee Symposium on Foundations of Computer Science (FOCS 2006) [pdf]

  • Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. Niv Buchbinder, Kamal Jain and Seffi Naor, 15th Annual European Symposium on Algorithms (ESA 2007) - Best Paper Award [pdf]

  • An O(log2k)-competitive Algorithm for Metric Bipartite Matching. Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Seffi Naor, 15th Annual European Symposium on Algorithms (ESA 2007) [pdf]

  • A Primal-Dual Randomized Algorithm for Weighted Paging. Nikhil Bansal, Niv Buchbinder and Seffi Naor, 48th annual ieee Symposium on Foundations of Computer Science (FOCS 2007).[pdf]

  • Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev and Maxim Sviridenko, (SODA 2008). [pdf]

  • Non-cooperative Cost Sharing Games via Subsidies. Niv Buchbinder, Liane Lewin-Eytan, Joseph (Seffi) Naor, Ariel Orda, 1st International Symposium on Algorithmic Game Theory (SAGT 2008). [pdf]

  • Randomized Competitive Algorithms for Generalized Caching. Nikhil Bansal, Niv Buchbinder and Seffi Naor, 40th Annual ACM Symposium on Theory of Computing (STOC 2008). [pdf]

  • Dynamic Power Allocation under Arbitrary Varying Channels -- An Online Approach. Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Seffi Naor and Ariel Orda, 28th Conference on Computer Communications (INFOCOM 2009). [pdf]

  • Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. Nikhil Bansal, Niv Buchbinder and Seffi Naor, ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). [pdf]

  • Dynamic Power Allocation under Arbitrary Varying Channels – The Multi-User Case. Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Seffi Naor and Ariel Orda, 29th Conference on Computer Communications (INFOCOM 2010). [pdf]

  • Secretary Problems via Linear Programming. Niv Buchbinder, Kamal Jain and Mohit Singh, 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010). [pdf]

  • A Regularization Approach to Metrical Task Systems. Jacob Abernethy, Peter Bartlett, Niv Buchbinder and Isabelle Stanton, Algorithmic Learning Theory, 21st International Conference (ALT 2010). [pdf]

  • Unfair Metrical Task Systems on HSTs and Applications. Nikhil Bansal, Niv Buchbinder and Seffi Naor, Automata, Languages and Programming, 37th International Colloquium (ICALP 2010). [pdf]

  • How to Allocate Goods in an Online Market? Yossi Azar, Niv Buchbinder and Kamal Jain, 18th Annual European Symposium on Algorithms ESA 2010. [pdf]

  • Incentives in Online Auctions via Linear Programming. Niv Buchbinder, Kamal Jain and Mohit Singh, Internet and Network Economics - 6th International Workshop, WINE 2010. [pdf]

  • Online Job-Migration for Reducing the Electricity Bill in the Cloud. Niv Buchbinder, Navendu Jain, Ishai Menache, the 10th International IFIP TC 6 Networking Conference (Networking 2011).

  • Frequency Capping in Online Advertising. Niv Buchbinder, Moran Feldman, Arpita Ghosh and Seffi Naor, Algorithms and Data Structures - 12th International Symposium, (WADS 2011).

  • A Polylogarithmic Competitive Algorithm for the k-Server Problem. Nikhil Bansal, Niv Buchbinder, Aleksander Madry and Seffi Naor, IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011) - Best Paper Award.

  • A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz, the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).

  • Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints. Niv Buchbinder, Joseph Naor, R. Ravi, Mohit Singh. The 39th International Colloquium on Automata, Languages and Programming (ICALP 2012).

  • Unified Algorithms for Online Learning and Competitive Analysis. Niv Buchbinder, Shahar Chen, Joseph Naor, Ohad Shamir, The 25th Conference on Learning Theory (COLT 2012).

  • Simplex Partitioning via Exponential Clocks and the Multiway Cut Problem. Niv Buchbinder, Seffi Naor, Roy Swartz. The 45th ACM Symposium on the Theory of Computing (STOC 2013).

  • Competitive Analysis via Regularization. Niv Buchbinder, Shahar Chen and Seffi Naor. The 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).

  • Submodular Maximization with Cardinality Constraints. Niv Buchbinder, Moran Feldman, Seffi Naor, Roy Schwartz. The 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).

  • Competitive Algorithms for Restricted Caching and Matroid Caching. Niv Buchbinder, Shahar Chen, Seffi Naor. The 22nd Annual European Symposium on Algorithms, (ESA 2014).

  • Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization. Niv Buchbinder, Moran Feldman, Roy Schwartz. To Appear in the 26th ACM-SIAM Symposium on Discrete Algorithms, (SODA 2015).

  • Online Submodular Maximization with Preemption. Niv Buchbinder, Moran Feldman, Roy Schwartz. To Appear in the 26th ACM-SIAM Symposium on Discrete Algorithms, (SODA 2015).

  • Deterministic Algorithms for Submodular Maximization Problems. Niv Buchbinder, Moran Feldman. The 27th ACM-SIAM Symposium on Discrete Algorithms, (SODA 2016). pp. 392-403.

  • Online Algorithms for Covering and Packing Problems with Convex Objectives. Y. Azar, N. Buchbinder, T.-H. H. Chan , S. Chen, I. R. Cohen, A. Gupta, Z. Huang, N. Kang, J. Naor , V. Nagarajan , D. Panigrahi. The 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). pp. 148-157.

  • Fair Coin Flipping: Tighter Analysis and the Many-Party Case. Niv Buchbinder, Iftach Haitner, Nissan Levi, Eliad Tsfadia. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. pp. 2580-2600.

  • Simplex Transformations and the Multiway Cut Problem. Niv Buchbinder, Roy Schwartz, Baruch Weizman. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 . pp. 2400-2410.

  • O(depth)-Competitive Algorithm for Online Multi-level Aggregation. Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Ohad Talmon. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. pp. 1235-1244.

  • Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. Niv Buchbinder, Danny Segev, Yevgeny Tkach. The 25th Annual European Symposium on Algorithms, ESA 2017. pp. 22:1 – 22:14

  • k-Servers with a Smile: Projection-based Algorithms for Online Problems. Niv Buchbinder, Anupam Gupta, Marco Molinaro and Joseph Naor. The Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)

  • Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid. Niv Buchbinder, Moran Feldman, Mohit Garg. The Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)

  • Online Submodular Maximization: Beating ½ Made Simple. Niv Buchbinder, Moran Feldman, Yuval Filmus, Mohit Garg. The 20th Conference on Integer Programming and Combinatorial Optimization (IPCO 2019)

  • Metrical Service Systems with Transformations. Sébastien Bubeck, Niv Buchbinder, Christian Coester, Mark Sellke. The 12th Innovations in Theoretical Computer Science Conference, (ITCS 2021), 21:1-21:20

  • Online k-Taxi via Double Coverage and Time-Reverse Primal-Dual. Niv Buchbinder, Christian Coester, Seffi Naor. Accepted to the 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021)

  • Online Virtual Machine Allocation with Lifetime and Load Predictions. Niv Buchbinder, Yaron Fairstein, Konstantina Mellou, Ishai Menache, Seffi Naor. Proceedings of the 2021 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2021)

Journal Publications

  • Lower and Upper Bounds on Obtaining History Independence. Niv Buchbinder and Erez Petrank. Information and Computation, volume 204, Issue 2 (February 2006), pp. 291-337.

  • A General Approach to Online Network Optimization Problems. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor. ACM Transactions on Algorithms, Volume 2, Number 4 (2006), pp. 640-660.

  • Non-cooperative Cost Sharing Games via Subsidies. Niv Buchbinder, Liane Lewin-Eytan, Joseph (Seffi) Naor, Ariel Orda, Theory of Computing Systems, Springer, volume 47,1, pages 15-37, 2010.

  • Online Primal-Dual Algorithms for Covering and Packing Problems. Niv Buchbinder and Seffi Naor, Mathematics of Operations Research Vol. 34, No. 2, May 2009, pp. 270-286

  • The Online Set Cover Problem. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Seffi Naor, SIAM J. Computing Volume 39, Issue 2, pp. 361-370 (2009)

  • A Primal-Dual Randomized Algorithm for Weighted Paging. Nikhil Bansal, Niv Buchbinder and Joseph (Seffi) Naor. J. ACM 59(4): 19 (2012).

  • Dynamic Power Allocation Under Arbitrary Varying Channels - An Online Approach. Niv Buchbinder, Liane Lewin-Eytan, Ishai Menache, Joseph Naor, Ariel Orda, IEEE/ACM Transactions on Networking 20(2): 477-487 (2012).

  • Randomized Competitive Algorithms for Generalized Caching. Nikhil Bansal, Niv Buchbinder, Joseph Naor, SIAM Journal on Computing 41(2): 391-414 (2012).

  • Fair Online Load Balancing. Niv Buchbinder and Joseph (Seffi) Naor. Journal of Scheduling 16(1): 117-127 (2013).

  • An O(log2k)-competitive Algorithm for Metric Bipartite Matching. Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Seffi Naor, Algorithmica. Volume 68, issue 2, pp. 390--403, 2014.

  • Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev and Maxim Sviridenko. Operations Research (OR). volume 61, issue 4, pp. 1014-1029, 2013.

  • Secretary Problems via Linear Programming. Niv Buchbinder, Kamal Jain and Mohit Singh. Math of OR. Volume 39, issue 1, pp. 190--206, 2014.

  • Incentive Compatible Mulit-Unit Combinatorial Auctions: A Primal Dual Approach. Niv Buchbinder and Rica Gonen. Algorithmica, volume 72, issue 1, pp. 167--190, 2015.

  • Frequency Capping in Online Advertising. Niv Buchbinder, Moran Feldman, Arpita Ghosh and Seffi Naor. Journal of Scheduling. Volume 17, issue 4, pp. 385--398, 2014.

  • Tight Linear Time ½ -Approximation for Unconstrained Submodular Maximization. Niv Buchbinder, Moran Feldman, Seffi Naor, Roy Schwartz. SIAM Journal on Computing (SICOMP), volume 44, issue 5, pp. 1384—1402, 2015. Special Issue of FOCS 2012.

  • A Polylogarithmic Competitive Algorithm for the k-Server Problem. Nikhil Bansal, Niv Buchbinder, Aleksander Madry and Seffi Naor. Journal of the ACM (JACM), volume 62, issue 5, pp. 40:1-40:49, 2015.

  • How to Allocate Goods in an Online Market? Yossi Azar, Niv Buchbinder and Kamal Jain. Algorithmica, volume 74, issue 2, pp. 589-601, 2016.

  • Unified Algorithms for Online Learning and Competitive Analysis. Niv Buchbinder, Shahar Chen, Seffi Naor and Ohad Shamir. Mathematics of Operations Research, volume 41, issue 2, pp. 612-625, 2016.

  • Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization. Niv Buchbinder, Moran Feldman, Roy Schwartz. Mathematics of Operations Research, volume 42, issue 2, pp. 308-329, 2017.

  • Simplex Partitioning via Exponential Clocks and the Multiway Cut Problem. Niv Buchbinder, Seffi Naor, Roy Schwartz. SIAM Journal on Computing (SICOMP) volume 47, issue 4, pp. 1463–1482, 2018.

  • Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. Niv Buchbinder, Danny Segev, Yevgeny Tkach. Algorithmica, volume 81(5): pp. 1781-1799, 2019.

  • Constrained Submodular Maximization via a Non-Symmetric Technique. Niv Buchbinder, Moran Feldman. Mathematics of Operations Research, volume 44(3), pp. 988-1005, 2019.

  • Deterministic Algorithms for Submodular Maximization Problems. Niv Buchbinder, Moran Feldman. ACM Transactions on Algorithms 14(3): 32:1-32:20 (2018) (Special issue of SODA 2016)

  • Online Submodular Maximization with Preemption. Niv Buchbinder, Moran Feldman, Roy Schwartz. ACM Trans. Algorithms 15(3): 30:1-30:31(2019)

  • A Simple Algorithm for the Multiway Cut Problem. Niv Buchbinder, Roy Schwartz, Baruch Weizman. Operations Research Letters, 47(6): 587-593, 2019.

  • Simplex Transformations and the Multiway Cut Problem. Niv Buchbinder, Roy Schwartz, Baruch Weizman. Accepted to Mathematics of Operations Research (MOR)

  • Online Submodular Maximization: Beating 1/2 Made Simple. Niv Buchbinder, Moran Feldman, Yuval Filmus, Mohit Garg. Math. Program. 183(1): 149-169 (2020) (Special issue of IPCO 2019)

PhD. Thesis

  • The Design of Competitive Online Algorithms via a Primal-Dual Approach. Advisor: Prof. Seffi Naor
    Computer Science Department, Technion, Israel, September 2008.     [pdf]

M.Sc. Thesis

  • Lower and Upper Bounds on Obtaining History Independence. Advisor: Prof. Erez Petrank

Computer Science Department, Technion, Israel, November 2003. [pdf]