Niv Buchbinder - Home Page

 

 

I am a faculty member in the Department of Statistics and Operations Research, School of Mathematical Sciences at Tel Aviv University.

My main area of research is algorithms for combinatorial optimization problems in offline and online settings. I am also interested in algorithmic game theory problems.

 

Contact Information

Office:

Phone:

Room 327, Schreiber Building, Tel Aviv University

972-3-6409356

E-mail:

niv.buchbinder@gmail.com

 


Courses

Survey book

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]

·        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).

 

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).

PhD. Thesis

M.Sc. Thesis

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

 שלום בוכבינדר  Shalom Buchbinder: חוברת זיכרון    [pdf] זכרונות ילדות,[ppt] תמונות, [pdf]