Niv Buchbinder

2024

Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

Buchbinder, N. & Feldman, M., 10 Jun 2024, STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Mohar, B., Shinkar, I. & O�Donnell, R. (eds.). p. 1820-1831 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Tel Aviv University, University of Haifa

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

Maintaining Matroid Intersections Online

Buchbinder, N., Gupta, A., Hathcock, D., Karlin, A. R. & Sarkar, S., 2024, p. 4283-4304. 22 p.

Tel Aviv University

Research output: Contribution to conference › Paper › peer-review

Open Access

2023

Chasing Positive Bodies

Bhattacharya, S., Buchbinder, N., Levin, R. & Saranurak, T., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1694-1714 21 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Tel Aviv University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

DETERMINISTIC (1/2+ϵ)-APPROXIMATION FOR SUBMODULAR MAXIMIZATION OVER A MATROID

Buchbinder, N., Feldman, M. & Garg, M., 2023, In: SIAM Journal on Computing. 52, 4, p. 945-967 23 p.

Tel Aviv University, Open University of Israel

Research output: Contribution to journal › Article › peer-review

Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)

Buchbinder, N., Naor, J. & Wajc, D., 2023, 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023. p. 2030-2068 39 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2023-January).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

Online k-taxi via Double Coverage and time-reverse primal-dual

Buchbinder, N., Coester, C. & Naor, J., Feb 2023, In: Mathematical Programming. 197, 2, p. 499-527 29 p.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Open Access

2021

Metrical service systems with transformations

Bubeck, S., Buchbinder, N., Coester, C. & Sellke, M., 1 Feb 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). 21. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).

Tel Aviv University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Online k-Taxi via Double Coverage and Time-Reverse Primal-Dual

Buchbinder, N., Coester, C. & Naor, J., 2021, Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings. Singh, M. & Williamson, D. P. (eds.). Springer Science and Business Media Deutschland GmbH, p. 15-29 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12707 LNCS).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Online Virtual Machine Allocation with Lifetime and Load Predictions

Buchbinder, N., Fairstein, Y., Mellou, K., Menache, I. & Naor, J., Jun 2021, In: Performance Evaluation Review. 49, 1, p. 9-10 2 p.

Tel Aviv University

Research output: Contribution to journal › Article › peer-review

Online Virtual Machine Allocation with Lifetime and Load Predictions

Buchbinder, N., Fairstein, Y., Mellou, K., Menache, I. & Naor, J. S., 31 May 2021, SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. p. 9-10 2 p. (SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Simplex transformations and the multiway cut problem

Buchbinder, N., Schwartz, R. & Weizman, B., May 2021, In: Mathematics of Operations Research. 46, 2, p. 757-771 15 p.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

2020

Online submodular maximization: beating 1/2 made simple

Buchbinder, N., Feldman, M., Filmus, Y. & Garg, M., 1 Sep 2020, In: Mathematical Programming. 183, 1-2, p. 149-169 21 p.

Tel Aviv University, Open University of Israel, University of Haifa, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Open Access

2019

A simple algorithm for the multiway cut problem

Buchbinder, N., Schwartz, R. & Weizman, B., Nov 2019, In: Operations Research Letters. 47, 6, p. 587-593 7 p.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Constrained submodular maximization via a nonsymmetric technique

Buchbinder, N. & Feldman, M., 2019, In: Mathematics of Operations Research. 44, 3, p. 988-1005 18 p.

Tel Aviv University, Open University of Israel

Research output: Contribution to journal › Article › peer-review

Open Access

Deterministic (¹/2 + ε)-approximation for submodular maximization over a matroid

Buchbinder, N., Feldman, M. & Garg, M., 2019, p. 241-254. 14 p.

Tel Aviv University, Open University of Israel

Research output: Contribution to conference › Paper › peer-review

K-servers with a smile: Online algorithms via projections

Buchbinder, N., Gupta, A., Molinaro, M. & Naor, J., 2019, p. 98-116. 19 p.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to conference › Paper › peer-review

Open Access

Online Algorithms for Maximum Cardinality Matching with Edge Arrivals

Buchbinder, N., Segev, D. & Tkach, Y., 15 May 2019, In: Algorithmica. 81, 5, p. 1781-1799 19 p.

Tel Aviv University, University of Haifa

Research output: Contribution to journal › Article › peer-review

Online Submodular Maximization: Beating 1/2 Made Simple

Buchbinder, N., Feldman, M., Filmus, Y. & Garg, M., 2019, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Lodi, A. & Nagarajan, V. (eds.). Vol. 11480. p. 101-114 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11480 LNCS).

Tel Aviv University, Open University of Israel, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

Online submodular maximization with preemption

Buchbinder, N., Feldman, M. & Schwartz, R., May 2019, In: ACM Transactions on Algorithms. 15, 3, 0076.

Tel Aviv University, Open University of Israel, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Open Access

2018

Deterministic algorithms for submodular maximization problems

Buchbinder, N. & Feldman, M., Jul 2018, In: ACM Transactions on Algorithms. 14, 3, 32.

Tel Aviv University, Open University of Israel

Research output: Contribution to journal › Article › peer-review

Open Access

Simplex partitioning via exponential clocks and the multiway-cut problem

Buchbinder, N., Naor, J. & Schwartz, R., 2018, In: SIAM Journal on Computing. 47, 4, p. 1463-1482 20 p.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Submodular Functions Maximization Problems.

Buchbinder, N. & Feldman, M., 2018, Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications. Gonzalez, T. F. (ed.). Boca Raton, Vol. 1. p. 753-788 36 p.

Tel Aviv University, University of Haifa

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

2017

Comparing apples and oranges: Query trade-off in submodular maximization

Buchbinder, N., Feldman, M. & Schwartz, R., May 2017, In: Mathematics of Operations Research. 42, 2, p. 308-329 22 p.

Tel Aviv University, Open University of Israel, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Open Access

Fair coin flipping: Tighter analysis and the many-party case

Buchbinder, N., Haitner, I., Levi, N. & Tsfadia, E., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). p. 2580-2600 21 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

Tel Aviv University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

O(depth)-Competitive algorithm for online multi-level aggregation

Buchbinder, N., Feldman, M., Naor, J. & Talmon, O., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). p. 1235-1244 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

Tel Aviv University, Open University of Israel, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

Online algorithms for maximum cardinality matching with edge arrivals

Buchbinder, N., Segev, D. & Tkach, Y., 1 Sep 2017, 25th European Symposium on Algorithms, ESA 2017. Sohler, C. & Pruhs, K. (eds.). 22. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 87).

Tel Aviv University, University of Haifa

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Simplex transformations and the multiway cut problem

Buchbinder, N., Schwartz, R. & Weizman, B., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). p. 2400-2410 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

2016

Deterministic algorithms for submodular maximization problems

Buchbinder, N. & Feldman, M., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). p. 392-403 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 1).

Tel Aviv University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

How to Allocate Goods in an Online Market?

Azar, Y., Buchbinder, N. & Jain, K., 1 Feb 2016, In: Algorithmica. 74, 2, p. 589-601 13 p.

Tel Aviv University

Research output: Contribution to journal › Article › peer-review

Online Algorithms for Covering and Packing Problems with Convex Objectives

Azar, Y., Buchbinder, N., Chan, T. H. H., Chen, S., Cohen, I. R., Gupta, A., Huang, Z., Kang, N., Nagarajan, V., Naor, J. & Panigrahi, D., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 148-157 10 p. 7782927. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Unified algorithms for online learning and competitive analysis

Buchbinder, N., Chen, S., Naor, J. S. & Shamir, O., May 2016, In: Mathematics of Operations Research. 41, 2, p. 612-625 14 p.

Tel Aviv University, Weizmann Institute of Science, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

2015

A polylogarithmic-competitive algorithm for the k-server problem

Bansal, N., Buchbinder, N., Madry, A. & Naor, J. S., Oct 2015, In: Journal of the ACM. 62, 5, 40.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Open Access

A tight linear time (1/2)-approximation for unconstrained submodular maximization

Buchbinder, N., Feldman, M., Naor, J. S. & Schwartz, R., 2015, In: SIAM Journal on Computing. 44, 5, p. 1384-1402 19 p.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Comparing apples and oranges: Query tradeoff in submodular maximization

Buchbinder, N., Feldman, M. & Schwartz, R., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. p. 1149-1168 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

Tel Aviv University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

Incentive Compatible Mulit-Unit Combinatorial Auctions: A Primal Dual Approach

Buchbinder, N. & Gonen, R., 1 May 2015, In: Algorithmica. 72, 1, p. 167-190 24 p.

Tel Aviv University, Open University of Israel

Research output: Contribution to journal › Article › peer-review

Online submodular maximization with preemption

Buchbinder, N., Feldman, M. & Schwartz, R., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. p. 1202-1216 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

Tel Aviv University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

2014

Competitive algorithms for restricted caching and matroid caching

Buchbinder, N., Chen, S. & Naor, J., 2014, Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings. p. 209-221 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8737 LNCS).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Competitive analysis via regularization

Buchbinder, N., Chen, S. & Naor, J., 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. p. 436-444 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Frequency capping in online advertising

Buchbinder, N., Feldman, M., Ghosh, A. & Naor, J., Aug 2014, In: Journal of Scheduling. 17, 4, p. 385-398 14 p.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Open Access

Secretary problems via linear programming

Buchbinder, N., Jain, K. & Singh, M., Feb 2014, In: Mathematics of Operations Research. 39, 1, p. 190-206 17 p.

Tel Aviv University

Research output: Contribution to journal › Article › peer-review

Submodular maximization with cardinality constraints

Buchbinder, N., Feldman, M., Naor, J. & Schwartz, R., 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. p. 1433-1452 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2013

Fair online load balancing

Buchbinder, N. & Naor, J., Feb 2013, In: Journal of Scheduling. 16, 1, p. 117-127 11 p.

Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Online make-to-order joint replenishment model: Primal-dual competitive algorithms

Buchbinder, N., Kimbrel, T., Levi, R., Makarychev, K. & Sviridenko, M., Jul 2013, In: Operations Research. 61, 4, p. 1014-1029 16 p.

Tel Aviv University

Research output: Contribution to journal › Article › peer-review

Simplex partitioning via exponential clocks and the multiway cut problem

Buchbinder, N., Naor, J. & Schwartz, R., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 535-544 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2012

Approximation algorithms for online weighted rank function maximization under matroid constraints

Buchbinder, N., Naor, J., Ravi, R. & Singh, M., 2012, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 ed. p. 145-156 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7391 LNCS, no. PART 1).

Open University of Israel, Technion - Israel Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

A primal-dual randomized algorithm for weighted paging

Bansal, N., Buchbinder, N. & Naor, J. S., Aug 2012, In: Journal of the ACM. 59, 4, 19.

Open University of Israel, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

A tight linear time (1/2)-approximation for unconstrained submodular maximization

Buchbinder, N., Feldman, M., Naor, J. & Schwartz, R., 2012, In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 649-658 10 p., 6375344.

Tel Aviv University, Technion - Israel Institute of Technology

Research output: Contribution to journal › Conference article › peer-review

Dynamic power allocation under arbitrary varying channels-anonline approach

Buchbinder, N., Lewin-Eytan, L., Menache, I., Naor, J. & Orda, A., Apr 2012, In: IEEE/ACM Transactions on Networking. 20, 2, p. 477-487 11 p., 6104402.

Open University of Israel, Technion - Israel Institute of Technology

Research output: Contribution to journal › Article › peer-review

Open Access