Copyright Notice: Most of these papers were published in journals or conference proceedings,
and the copyright has been transferred to the publisher. The posting here is only for
non-commercial and personal use.
Similar lists of my publications can also be found at DBLP, Google Scholar and ORCID.
Optimization of Submodular Set Functions (Offline)
- Niv Buchbinder and Moran Feldman:
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
submitted.
- Murad Tukan, Loay Mualem and Moran Feldman:
Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint
to appear in NeurIPS 2024.
- Niv Buchbinder and Moran Feldman:
Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
in FOCS 2024. [YouTube]
- Niv Buchbinder and Moran Feldman:
Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
in STOC 2024, pages 1820-1831. [pptx] [YouTube]
- Loay Mualem, Ethan Elenberg, Moran Feldman and Amin Karbasi:
Submodular Minimax Optimization: Finding Effective Sets
in AISTATS 2024, pages 1081-1089.
- Moran Feldman, Zeev Nutov and Elad Shoham:
Practical Budgeted Submodular Maximization
Algorithmica, volume 85, issue 5, pages 1332-1371, May 2023.
Associated resource: The above link leads to the arXiv version of the paper. A read-only copy of the journal version of this paper is available here.
- Wenxin Li, Moran Feldman, Ehsan Kazemi and Amin Karbasi:
Submodular Maximization in Clean Linear Time
in NeurIPS 2022, pages 17473-17487.
- Loay Mualem and Moran Feldman:
Using Partial Monotonicity in Submodular Maximization
in NeurIPS 2022, pages 2723-2736.
Associated resources: The above link leads to the arXiv version of the paper. The conference version includes a stronger (and tight) algorithmic result for the unconstrained case, and can be found here.
- Kobi Bodek and Moran Feldman:
Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case
in ESA 2022, pages 23:1-23:17.
- Moran Feldman:
Guess Free Maximization of Submodular and Linear Sums
Algorithmica, volume 83, issue 3, pages 853-878, March 2021,
an extended abstract appeared in WADS 2019, pages 380-394. [pptx]
Associated resources: The above link leads to the arXiv version of the paper. The journal version of the paper includes a somewhat stronger algorithmic result as well as a matching hardness result, and a read-only copy of this version is available here. An erratum fixing some minor mistakes in the journal version can be found here.
- Niv Buchbinder and Moran Feldman:
Constrained Submodular Maximization via a Non-symmetric Technique
Mathematics of Operations Research, volume 44, issue 3, pages 988-1005, August 2019.
- Lin Chen, Moran Feldman and Amin Karbsai:
Unconstrained Submodular Maximization with Constant Adaptive Complexity
in STOC 2019, pages 102-113.
- Niv Buchbinder, Moran Feldman and Mohit Garg:
Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid
SIAM Journal on Computing, volume 52, issue 4, pages 945-967, August 2023,
an extended abstract appeared in SODA 2019, pages 241-254.
- Niv Buchbinder and Moran Feldman:
Submodular Functions Maximization Problems - A Survey
in Handbook of Approximation Algorithms and Metaheuristics (Second Edition, ed. Teofilo F. Gonzalez), volume 1, chapter 42, 2018.
- Moran Feldman, Chris Harshaw and Amin Karbasi:
How Do You Want Your Greedy: Simultaneous or Repeated?
Journal of Machine Learning Research, volume 24, number 72, pages 1-87, April 2023.
This paper includes the deterministic results of the extended abstract Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization
that appeared in COLT 2017 (pages 758-784) as well as new results.
- Niv Buchbinder and Moran Feldman:
Deterministic Algorithms for Submodular Maximization Problems
ACM Transactions on Algorithms, volume 14, issue 3, pages 32:1-32:20, July 2018 (special issue of SODA 2016, winner of the 2018 Rothblum prize awarded by the Operations Research Society of Israel),
an extended abstract appeared in SODA 2016, pages 392-403. [pptx]
- Moran Feldman:
Maximizing Symmetric Submodular Functions
ACM Transactions on Algorithms, volume 13, issue 3, pages 39:1-39:36, May 2017,
an extended abstract appeared in ESA 2015, pages 521-532. [pptx]
- Niv Buchbinder, Moran Feldman and Roy Schwartz:
Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization
Mathematics of Operations Research, volume 42, issue 2, pages 308-329, May 2017,
an extended abstract appeared in SODA 2015, pages 1149-1168.
- Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz:
Submodular Maximization with Cardinality Constraints
in SODA 2014, pages 1433-1452. [pptx]
- Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz:
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
SIAM Journal on Computing, volume 44, issue 5, pages 1384-1402, October 2015 (special issue of FOCS 2012, winner of the 2017 SIAM Outstanding Paper Prize),
an extended abstract appeared in FOCS 2012, pages 649-658 (recipient of the 10-year FOCS Test of Time award).
- Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz and Justin Ward:
Improved Approximations for k-Exchange Systems.
in ESA 2011, pages 784-798.
- Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz:
A Unified Continuous Greedy Algorithm for Submodular Maximization
in FOCS 2011, pages 570-579. [pptx]
Associated resource: A version of this paper with full proofs is available here.
- Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz:
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm
in ICALP 2011, pages 342-353.
Optimization of Submodular Set Functions (Online and Streaming)
- Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson and Rico Zenklusen:
Submodular Maximization Subject to Matroid Intersection on the Fly
in ESA 2022, pages 52:1-52:14.
- Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson and Rico Zenklusen:
Streaming Submodular Maximization under Matroid Constraints
in ICALP 2022, pages 59:1-59:20.
- Ehsan Kazemi, Shervin Minaee, Moran Feldman and Amin Karbasi:
Regularized Submodular Maximization at Scale
in ICML 2021, pages 5356-5366. [YouTube]
- Ran Haba, Ehsan Kazemi, Moran Feldman and Amin Karbasi:
Streaming Submodular Maximization under a k-Set System Constraint
in ICML 2020, pages 1842-1852.
This paper subsumes a previous pre-print that had a different title and contained only the result for linear objective functions.
- Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen and Andrew Suh:
Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints
Mathematics of Operations Research, volume 47, issue 4, pages 2667-2690, November 2022,
an extended abstract appeared in ICALP 2020, pages 6:1-6:19. [YouTube]
This paper is a merger of two previous pre-prints titled An Optimal Streaming Algorithm for Non-monotone Submodular Maximization and Making a Sieve Random: Improved Semi-Streaming Algorithm for Submodular Maximization under a Cardinality Constraint.
- Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson and Rico Zenklusen:
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Journal of the ACM, volume 70, issue 4, pages 24:1-24:52, August 2023,
an extended abstract appeared in STOC 2020, pages 1363-1374. [YouTube]
- Niv Buchbinder, Moran Feldman, Yuval Filmus and Mohit Garg:
Online Submodular Maximization: Beating 1/2 Made Simple
Mathematical Programming, volume 183, issue 1, pages 149-169, September 2020 (special issue of IPCO 2019),
an extended abstract appeared in IPCO 2019, pages 101-114.
Associated resource: The above links to the arXiv version of the paper. The journal version of the paper includes a somewhat stronger hardness result, and a read-only copy of this version is available here.
- Christopher Harshaw, Ehsan Kazemi, Moran Feldman and Amin Karbasi:
The Power of Subsampling in Submodular Maximization
Mathematics of Operations Research, volume 47, issue 2, pages 1365-1393, May 2022.
This paper is based on an extended abstract titled
Do Less, Get More: Streaming Submodular Maximization with Subsampling that appeared in NeurIPS 2018 (pages 730-740), but also includes the randomization based results of an extended abstract titled Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization that appeared in COLT 2017 (pages 758-784).
- Moran Feldman and Rico Zenklusen:
The Submodular Secretary Problem Goes Linear
SIAM Journal on Computing, volume 47, issue 2, pages 330-366, April 2018,
an extended abstract appeared in FOCS 2015, pages 486-505.
- Niv Buchbinder, Moran Feldman and Roy Schwartz:
Online Submodular Maximization with Preemption
ACM Transactions on Algorithms, volume 15, issue 3, pages 30:1-30:31, July 2019,
an extended abstract appeared in SODA 2015, pages 1202-1216.
- Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz:
Improved Competitive Ratios for Submodular Secretary Problems
in APPROX 2011, pages 218-229. [pptx]
Associated resource: A version of this paper with full proofs is available here.
Optimization of other Combinatorial Functions
- Loay Mualem, Murad Tukan and Moran Feldman:
Bridging the Gap Between General and Down-Closed Convex Sets
in Submodular Maximization
in IJCAI 2024, pages 1926-1934.
- Loay Mualem and Moran Feldman:
Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets
in AISTATS 2023, pages 2542-2564.
- Siddharth Mitra, Moran Feldman and Amin Karbasi:
Submodular + Concave
in NeurIPS 2021, pages 11577-11591. [PaperTalk]
- Moran Feldman and Amin Karbasi:
Continuous Submodular Maximization: Beyond DR-Submodularity
in NeurIPS 2020, pages 1404-1416. [SlidesLive]
- Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause and Amin Karbasi:
Adaptive Sequence Submodularity
in NeurIPS 2019, pages 5353-5364.
- Chris Harshaw, Moran Feldman, Justin Ward and Amin Karbasi:
Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
in ICML 2019, pages 2634-2643.
- Lin Chen, Moran Feldman and Amin Karbasi:
Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
in ICML 2018, pages 803-812.
- Marko Mitrovic, Moran Feldman, Andreas Krause and Amin Karbasi:
Submodularity on Hypergraph: From Sets to Sequences
in AISTATS 2018, pages 1177-1184.
- Ethan R. Elenberg, Alexandros G. Dimakis, Moran Feldman and Amin Karbasi:
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly
in NIPS 2017, pages 4047-4057.
- Moran Feldman and Rani Izsak:
Building a Good Team: Secretary Problems and the Supermodular Degree
in SODA 2017, pages 1651-1670.
- Moran Feldman and Rani Izsak:
Constrained Monotone Function Maximization and the Supermodular Degree
in APPROX 2014, pages 160-175.
Online and Streaming Problems
- Moran Feldman and Ariel Szarf:
Maximum Matching sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model
Algorithmica, volume 86, pages 1173-1209, April 2024,
an extended abstract appeared in APPROX 2022, pages 33:1-33:24. [YouTube]
Associated resource: The above links to the arXiv version of the paper. The journal version of the paper includes additional graphical aids for the proofs as well as a tight example for one of the algorithms. A read-only copy of this version is available here.
- Moran Feldman:
Algorithms for Big Data (Book)
published by World Scientific on August 2020, 460 pages.
- Moran Feldman, Ola Svensson and Rico Zenklusen:
A Framework for the Secretary Problem on the Intersection of Matroids
SIAM Journal on Computing, volume 51, issue 3, pages 766-819, June 2022,
an extended abstract appeared in SODA 2018, pages 735-752. [pptx]
- Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor and Ohad Talmon:
O(depth)-Competitive Algorithm for Online Multi-level Aggregation
in SODA 2017, pages 1235-1244.
- Moran Feldman, Ola Svensson and Rico Zenklusen:
Online Contention Resolution Schemes with Applications to Bayesian Selection Problems
SIAM Journal on Computing, volume 50, issue 2, pages 255-300, March 2021,
an extended abstract appeared in SODA 2016, pages 1014-1033.
- Moran Feldman, Ola Svensson and Rico Zenklusen:
A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
Mathematics of Operations Research, volume 43, issue 2, pages 638-650, May 2018,
an extended abstract appeared in SODA 2015, pages 1189-1201.
- Moran Feldman and Moshe Tennenholtz:
Interviewing Secretaries in Parallel
in EC 2012, pages 550-567. [pptx]
Associated resource: A version of the paper with full proofs is available here.
- Niv Buchbinder, Moran Feldman, Arpita Ghosh and Jossef (Seffi) Naor:
Frequency Capping in Online Advertising
Journal of Scheduling, volume 17, issue 4, pages 385-398, August 2014,
an extended abstract appeared in WADS 2011, pages 147-158. [pptx]
- Moran Feldman and Jossef (Seffi) Naor:
Non-Preemptive Buffer Management for Latency Sensitive Packets
Journal of Scheduling, volume 20, issue 4, pages 337 353, August 2017,
an extended abstract appeared in INFOCOM 2010, pages 186-190. [pptx]
Algorithmic Game Theory and Auctions
- Moran Feldman, Gonen Frim and Rica Gonen:
Multi-sided Advertising Markets: Dynamic Mechanisms and Incremental User Compensations (the link points to an older version with a different title and a subset of the authors)
in GameSec 2018, pages 227-247.
- Moran Feldman and Rica Gonen:
Removal and Threshold Pricing: Truthful Two-Sided Markets with Multi-dimensional Participants (the link points to an older version with a different title)
in SAGT 2018, pages 163-175.
- Noga Alon, Moran Feldman and Moshe Tennenholtz:
Revenue and Reserve Prices in a Probabilistic Single Item Auction
Algorithmica, volume 77, issue 1, pages 1-15, January 2017.
- Moran Feldman, Moshe Tennenholtz and Omri Weinstein:
Distributed Signaling Games
ACM Transactions on Economics and Computation, volume 8, issue 2, pages 7:1-7:26, May 2020,
an extended abstract appeared in ESA 2016, pages 41:1-41:16.
- Moshe Babaioff, Moran Feldman and Moshe Tennenholtz:
Mechanism Design with Strategic Mediators
ACM Transactions on Economics and Computation, volume 4, issue 2, pages 7:1-7:48, January 2016,
an extended abstract appeared in ITCS 2015, pages 307-316. [pptx]
- Moran Feldman, Reshef Meir and Moshe Tennenholtz:
Competition in the Presence of Social Networks: How Many Service Providers Maximize
Welfare?
in WINE 2013, pages 174-187.
- Moran Feldman, Liane Lewin-Eytan and Jossef (Seffi) Naor:
Hedonic Clustering Games
Transactions on Parallel Computing, volume 2, issue 1, pages 4:1-4:48, May 2015 (special issue of SPAA 2012),
an extended abstract appeared in SPAA 2012, pages 267-276. [pptx]
Associated resource: NoNashValidation.vb
Approximation Algorithms
- Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai and Tami Tamir:
All-or-Nothing Generalized Assignment with Applications to Scheduling Advertising Campaigns
ACM Transactions on Algorithms, volume 12, issue 3, pages 38:1-38:25, June 2016,
an extended abstract appeared in IPCO 2013, pages 13-24.
- Moran Feldman, Guy Kortsarz and Zehev Nutov:
Improved Approximation Algorithms for Directed Steiner Forest
Journal of Computer and System Sciences, volume 78, issue 1, pages 279-292, January 2012,
an extended abstract appeared in SODA 2009, pages 922-931. [ppt]
Data Mining and Search
- Moran Feldman, Ronny Lempel, Oren Somekh and Kolman Vornovitsky:
On the Impact of Random Index-Partitioning on Index Compression
available in a preprint version only, July 2011.
- Munmun De Choudhury, Moran Feldman, Sihem Amer-Yahia, Niv Golbandi, Ronny Lempel and Cong Yu:
Automatic Construction of Travel Itineraries using Social Breadcrumbs
in Hypertext 2010, pages 35-44.
- Munmun De Choudhury, Moran Feldman, Sihem Amer-Yahia, Niv Golbandi, Ronny Lempel and Cong Yu:
Constructing Travel Itineraries from Tagged Geo-temporal Breadcrumbs
in WWW 2010.
Ad-hoc and Sensor Networks
- Moran Feldman and Sharoni Feldman:
Effective Management and Energy efficiency in Management of Very Large Scale Sensor Network
Sensors and Transducers Journal, volume 14, issue 1, pages 46-63, March 2012,
an extended abstract appeared in SENSORCOMM 2011, pages 45-50.
- Yossi Ben-Asher, Sharoni Feldman, Moran Feldman and Pini Gurfil:
Scalability Issues in Ad Hoc Networking: Metrical Routing vs. Table-driven Routing.
Wireless Personal Communications (Springer), volume 52, issue 3, pages 423-447, February 2010,
an extended abstract appeared in ITRE 2006, pages 61-68.
-
Yossi Ben-Asher, Sharoni Feldman, Pini Gurfil and Moran Feldman:
Hierarchical Task Assignment and Communication Algorithms for Unmanned Aerial Vehicle Flocks
Journal of Aerospace Computing, Information, and Communication, volume 5, issue 8, pages 234-250, August 2008.
-
Yossi Ben-Asher, Sharoni Feldman, Pini Gurfil and Moran Feldman:
Distributed decision and control for cooperative UAVs using Ad-Hoc communication
IEEE Transactions on Control Systems Technology, volume 16, issue 3, pages 511-516, May 2008,
an extended abstract appeared in IACAS 2006, pages 238-239.
- Yossi Ben-Asher, Sharoni Feldman and Moran Feldman:
Dynamic multipath allocation in Ad Hoc networks
The Computer Journal (Oxford Journals), volume 54, issue 2, pages 197-212, Feburary 2011,
an extended abstract appeared in MESH 2008.
- Pini Gurfil, Sharoni Feldman and Moran Feldman:
Coordination and Communication of Cooperative Parafoils for Humanitarian Aid
IEEE Transactions on Aerospace and Electronic Systems, volume 46, issue 4, pages
1747-1761, October 2010,
an extended abstract appeared in IACAS 2008, pages 379-415.
- Yossi Ben-Asher, Moran Feldman, Sharoni Feldman and Pini Gurfil:
IFAS: Interactive Flexible Ad hoc Simulator
Simulation Modeling Practice and Theory, volume 15, issue 7, pages 817-830, August 2007.
- Yossi Ben-Asher, Moran Feldman and Sharoni Feldman:
Ad-hoc Routing Using Virtual Coordinates Based on Rooted Trees
in SUTC 2006, pages 6-13.
Theses
