Publication Topics

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.

Optimization of Submodular Set Functions

• Naor Alaluf and Moran Feldman:
  Making a Sieve Random: Improved Semi-Streaming Algorithm for Submodular Maximization under a Cardinality Constraint
  submitted.


• Moran Feldman:
  Guess Free Maximization of Submodular and Linear Sums
  in WADS 2019, pages 380-394. [pptx]


• 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, Yuval Filmus and Mohit Garg:
  Online Submodular Maximization: Beating 1/2 Made Simple
  in IPCO 2019, pages 101-114.


• Niv Buchbinder, Moran Feldman and Mohit Garg:
  Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid
  in SODA 2019, pages 241-254.


• Moran Feldman, Amin Karbasi and Ehsan Kazemi:
  Do Less, Get More: Streaming Submodular Maximization with Subsampling
  in NeurIPS 2018, pages 730-740.


• 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:
  Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization
  in COLT 2017, pages 758-784.


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


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


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


• 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]


• Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz:
  Improved Competitive Ratios for Submodular Secretary Problems
  in APPROX 2011, pages 218-229. [pptx]


• 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 Other Set and Sequence Functions

• Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause and Amin Karbasi:
  Adaptive Sequence Submodularity
  to appear in NeurIPS 2019.


• 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 Ran Haba:
  Almost Optimal Semi-streaming Maximization for k-Extendible Systems
  submitted.


• Moran Feldman, Ola Svensson and Rico Zenklusen:
  Framework for the Secretary Problem on the Intersection of Matroids
  in SODA 2018, pages 735-752. [pptx]


• Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor and Ohad Talmon:
  Improved Bounds for Online Multi-level Aggregation
  in SODA 2017, pages 1235-1244.


• Moran Feldman, Ola Svensson and Rico Zenklusen:
  Online Contention Resolution Schemes
  in SODA 2016, 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]


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