Efficient and Practical Approximation Algorithms for Advertising in Content Feeds

Aristides Gionis; Guangyi Zhang; Ilie Sarpe

REVIEW 3 major objections 4 minor 32 references

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Two backwards greedy algorithms place ads in content feeds with a provable factor-2 revenue guarantee, improving the previous best practical factor of 4.

desk verdict The 2-approximation is correct—the stress-test counterexample misfires—but the paper has fixable presentation bugs and deserves serious review. read the letter →

arxiv 2502.02115 v1 pith:PZLPEE5L submitted 2025-02-04 cs.DS

Guangyi Zhang , Ilie Sarpe , Aristides Gionis This is my paper · ORCID

classification cs.DS MSC 68W2568R10

keywords contentfeedadvertisingStrmAdsapproximationalgorithmsbackwardsgreedynon-obliviousdecayingattentionrewarddecompositionempiricalevaluation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that the native-advertising problem StrmAds, where ads are inserted into a content feed and user attention decays with each item or ad seen, can be solved to within a factor of 2 of optimal expected revenue by two greedy algorithms that scan the feed from the bottom slot upward. The first algorithm uses exact marginal revenue gains; the second uses a lower bound derived from a new decomposition of the expected-reward function, making it faster while keeping the same guarantee. The same backward technique is claimed to solve the repeatable-ads variant exactly. If these results hold, content-feed platforms could replace flow-based ad allocation, whose practical guarantee is only a factor of 4, with a simple backward scan that carries a provable quality promise. The paper also provides the first broad empirical evaluation of the problem, reporting that the proposed methods match or beat existing heuristics on both synthetic and real advertising data.

What carries the argument

The load-bearing identity is the reward decomposition $R_j = \sum_{j'>j} (1-q)^{j'-j}\mathbf{1}[e_{j'}\in M](r_{e_{j'}} - q R_{j'})$, which expresses the expected revenue of a matching on slots $j+1,\dots,m$ as a backward cumulative sum of marginal gains. Around it the algorithms maintain per-ad potentials $\tau_i$, updated as $\tau_i = r_{ij} - q f_j(M)$ each time ad $i$ is (re-)assigned to slot $j$, and use the non-oblivious greedy criterion $\arg\max_i \{ r_{ij} - q f_j(M) - \tau_i (1-q)^{\sigma(i)-j} \}$, proved to be a lower bound on the true marginal gain. Processing slots backwards ensures that a decision at slot $j$ cannot disturb the already-fixed suffix, and the potentials $\Gamma_i = \tau_i (1-q)^{\sigma(i)-j}$ serve as reusable charging tokens in the factor-2 argument. The decomposition also yields the monotone non-increasing behaviour of suffix rewards used throughout the proof.

What would settle it

Run G-bpx on small random instances (say $m=7$ slots, $n=5$ ads, with $q\in\{0.1,0.3,0.5\}$ and adversarially drawn rewards), brute-force the optimal matching, and check the ratio; any instance with $f(\mathrm{G\text{-}bpx}) < f(\mathrm{OPT})/2$ refutes Theorem 5. Independently, from the algorithm's own trace one can verify at each backward step whether $2 f_j(\mathrm{ALG}_j) = \sum_{j'>j} g_{j'}(1-q)^{j'-j} + \sum_{e=(i,j')\in \mathrm{ALG}_j} \Gamma_i$ holds; the first violated step pinpoints where the charging argument would break.

Watch

Extended reading notes

Core claim

The paper's central claim is that the StrmAds problem, which seeks a matching between ads and feed slots that maximizes expected revenue under decaying user attention, admits a 2-approximation by two backwards greedy algorithms: G-bwd, which uses exact marginal gains, and G-bpx, which uses a lower-bound marginal gain and is faster. The proof proceeds by scanning slots from last to first, so that a decision at slot $j$ cannot disturb the already-fixed suffix, and by decomposing the objective into a backward cumulative sum of marginal gains, $R_j = \sum_{j'>j} (1-q)^{j'-j}\mathbf{1}[e_{j'}\in M](r_{e_{j'}} - q R_{j'})$. A charging argument with per-ad potentials $\Gamma_i = \tau_i (1-q)^{\sigma(i)-j}$ then shows that twice the greedy revenue covers the optimal revenue, giving the factor 2, which is tight because at $q=0$ the problem reduces to maximum-weight matching. For the variant where ads may be repeated (StrmAds-R), the same backward greedy is claimed to solve the problem exactly. The paper's counter-intuitive design principle is that the top slots are not where the quality guarantee is won; protecting the bottom slots is what makes the charging go through.

Load-bearing premise

The factor-2 guarantee rests on an accounting identity that the proof asserts without derivation: every unit of revenue in an optimal placement must be chargeable either to one greedy step's gain or to one unused ad potential, with each potential used at most once.

Editorial extensions

If this is right

If the 2-approximation theorems hold, content-feed platforms can replace the flow-based 4-approximation with a single backward scan over slots while doubling the worst-case revenue guarantee.
The factor 2 is tight for both proposed algorithms even when the problem degenerates to maximum-weight matching ($q=0$), as shown by Proposition 6.
The StrmAds-R variant, where ads may be repeated, is solved exactly by the backward greedy, giving an efficient optimal method when ad repetition is allowed.
The expected-reward function is neither monotone nor submodular, so the result is not obtainable by standard submodular maximization; the backward decomposition is the enabling device.
The empirical study, described as the first for this problem, shows the proposed methods match or outperform existing heuristics on synthetic and real data, with G-bpx notably faster than G-bwd.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension: if the asserted charging identity is verified on random instances, the same backward decomposition technique should transfer to other cascade models where an early intervention reduces later rewards, such as sponsored-search or recommendation sessions.
The paper leaves implicit that the printed pseudocode of G-bwd enforces a matching, while the optimality theorem for repeatable ads assumes ads can be reused; an implementation following the pseudocode would solve StrmAds rather than StrmAds-R, so the exactness claim needs the algorithm stated in a variant form.
Because the factor 2 is proved tight at $q=0$, any further worst-case improvement would have to leave the greedy class entirely, for instance by LP rounding; the experiments suggest that typical instances behave much better than the worst case.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main 2-approximation claim is real, and the stress-test counterexample against Theorem 5 does not survive inspection. For that m=2, q=1/2 instance, the correct value of R0 is 5/8, not 3/4; the mistake is replacing the marginal term in Eq. (5) with tau_2 instead of using the edge at slot 1. Once you compute g1 = 3/4, g2 = 1, Gamma1 = 3/8, Gamma2 = 1/4, the identity 2 f_0 = sum g + sum Gamma holds exactly (5/4 = 5/8 + 5/8). In fact, the identity follows for any run of the algorithm: the sum of g terms telescopes to f_j, and the Gamma sum equals f_j by the decomposition in Eq. (6) together with the definition of tau_i. The proof is terse, but not wrong.

What is genuinely new and good: the backwards-greedy viewpoint, the non-oblivious lower-bound greedy with tau potentials, and the jump from a 4-approx flow algorithm to a 2-approx linear-time greedy. The decomposition in Eqs. (5)-(6) is clean and the tightness example at q=0 correctly reduces to the known greedy 2-approx for MWM. The paper also ships the first public benchmark for this problem, with code and synthetic-plus-real-data experiments. That is real contribution.

The soft spots are real but modest. Algorithm 1's pseudo-code lines 5-6 always enforce a matching, so as printed it does not solve StrmAds-R; the proof of Theorem 2 only goes through if that check is skipped for the repeatable variant. That is a fixable presentation bug, not a mathematical one. The sentence in Section 2 claiming StrmAds-R "explicitly disallows consecutive ads" is simply false under the model, and Example 2 itself uses consecutive ads. The experiments never compare against an optimal solution—only against other heuristics—so the empirical claim of "strong performance" would be more convincing with an optimal baseline on small instances. Finally, the "This immediately implies" step in Theorem 5 deserves a two-line derivation; right now a referee has to fill it in.

This paper is for people working on ad allocation and greedy approximation algorithms. It is a solid, publishable result with fixable presentation problems. Send it to peer review; a serious referee can clean up the pseudo-code and the text without changing the core contribution.

Referee Report

3 major / 4 minor

Summary. The paper studies StrmAds, the problem of placing ads in content feeds under decaying user attention, introduced by Ieong et al. The main contributions are two backwards greedy algorithms: G-bwd, claimed to be exact for the variant where ads may repeat (StrmAds-R) and a 2-approximation for the general StrmAds problem, and G-bpx, a non-oblivious backwards greedy that is also claimed to be a 2-approximation for StrmAds. The paper also presents the first extensive empirical evaluation of algorithms for this problem, comparing the proposed methods against flow-based, matching-based, and online baselines on synthetic and real-data-derived instances. The theoretical claims improve the best-known practical approximation factor from 4 to 2.

Significance. If the guarantees hold, the paper makes a valuable practical and theoretical contribution: it provides simple, fast greedy algorithms with a provable factor-2 approximation for a problem whose previous practical guarantee was only 4. The backwards design and the non-oblivious potential-based charging scheme are interesting ideas that may transfer to other settings with externalities. The empirical study is thorough and the source code is public, which strengthens the reproducibility of the claims. However, the central proof of the 2-approximation is incomplete as written, and the pseudocode for the exact StrmAds-R algorithm contradicts its own problem definition. These issues are repairable, but they currently block verification of the main claims.

major comments (3)

[Appendix A, proof of Theorem 5] The proof asserts, with no derivation, the charging identity 2 f_j(ALG_j) = sum_{j'>j} g_{j'}(1-q)^{j'-j} + sum_{e=(i,j') in ALG_j} Γ_i. The first sum telescopes to R_j, so the identity is equivalent to R_j = sum_{i in ALG_j} τ_i(1-q)^{σ(i)-j}. This latter equality requires an invariant that each τ_i for an ad in the current matching equals r_{iσ(i)} - q f_{σ(i)}(ALG_j). Such an invariant is neither stated nor proved; it is not immediate from the update rule because f_{j'}(M) can change when another ad is later moved out of the suffix, and the paper does not show that every such change triggers a refresh of τ_i. Since the entire induction and the factor-2 guarantee rest on this equality, the proof is incomplete. (For the m=2, q=1/2 instance suggested as a counterexample, a direct computation with the paper's definitions gives f_0(ALG_0)=5/8, not 3/4, and the identity holds; however, the missing derivation remains.)
[Section 4.1] The pseudocode of Algorithm 1 enforces a matching through lines 5-6: whenever an ad is considered, any previous occurrence of that ad is removed. This prevents an ad from being assigned to more than one slot, which contradicts the StrmAds-R definition where ads may be displayed multiple times. The proof of Theorem 2 explicitly relies on ads being reusable. For a concrete instance, take q=0, r11=1, r12=1+ε, r22=1: the repeatable-ads optimum is 2+ε, while the printed algorithm returns at most 1+ε. The pseudocode must be modified (e.g., a slot-capacity-only validity check for StrmAds-R) or Theorem 2 must be restricted to the matching-constrained setting.
[Appendix A] The proof of Corollary 7 is presented as a sketch that is 'similar to Theorem 5' and introduces κ_ij without proving the analogous charging identity. Since Corollary 7 establishes the 2-approximation for Algorithm 1, it should be made self-contained after the proof of Theorem 5 is repaired. As written, the reader cannot verify the charging argument from the provided text.

minor comments (4)

[Section 4.2] Typo: 'preforms' should be 'performs'. Additionally, the sentence 'The G-bpx algorithm preforms an ad (re-)assignment' appears before the algorithm is fully described; consider moving it after the pseudocode.
[Section 4.2] The definition of σ(i) is clear for matched ads, but the paper should explicitly state that for ads never matched, σ(i) is only a local variable used in the current iteration and does not affect the output.
[Appendix A] The chain of inequalities leading to g ≥ r_ij - q R_j - τ_i(1-q)^{j̃-j}+1 is correct, but the final step would benefit from a one-line explanation that (1-q) ≤ 1.
[Section 6.3] In Table 1, the column header 'r_e ([min - max])' is ambiguous; it should be 'r_{ij}' or clarified in the caption.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the greedy analyses use self-contained potentials; the two flagged gaps are proof/spec errors, not input-output equivalences.

full rationale

The paper's claimed derivation chain is self-contained and does not reduce any prediction to its inputs. The 2-approximation proofs for G-bpx (Theorem 5) and G-bwd (Corollary 7) rest on potential functions tau_i defined by the explicit update rule tau_i = r_ij - q f_j(M) (Eq. 4), and on the decomposition R_j = sum (1-q)^{j'-j}(r_e - q R_{j'}) (Eq. 6), which follows algebraically from the objective in Eq. (1); neither step fits a parameter to data nor assumes the target inequality. The improvement from 4 to 2 is benchmarked against the external problem formulation and 4-approximation algorithm of Ieong et al. (2014), whose authors do not overlap with the present paper, and no load-bearing self-citation occurs anywhere in the reference list. Two verification concerns are noted but they are correctness risks, not circularity: the proof of Theorem 5 compresses the identity 2 f_j = sum g + sum Gamma into 'This immediately implies' without derivation, and the printed pseudocode of Algorithm 1 enforces a matching in lines 5-6 while Theorem 2 claims optimality for the repeatable-ad variant StrmAds-R; both are mathematical/specification gaps that would require repair, but neither is an input-output equivalence or a fitted prediction. The central claims therefore have independent content and the circularity score is 0.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

No new physical or domain entities are postulated. The tau_i potentials and the backwards ordering are algorithmic devices with no independent empirical handle; they are part of the algorithm, not invented entities in the sense of the ledger. All free parameters belong to the experimental design or baselines; the theoretical guarantee has no fitted constants.

free parameters (5)

quitting probability q (experimental input) = 0.1 default; swept over 0.25, 0.5, 0.75
Model input from Ieong et al.; fixed or swept in Section 6.2, not fitted to data.
G-onl threshold C_thr = best reward of an ad allocation to the first slot
Baseline heuristic parameter; the authors note G-onl is very sensitive to it and hard to set online (Section 6.1).
category-match multipliers alpha_k (YouTube instances) = 0.8 (matching category), 0.01 (otherwise)
Hand-chosen in Appendix B to shape the reward structure of the simulated native-advertising instances.
browsing transition probability p (YouTube instances) = 0.5
Hand-chosen in Appendix B for the simulated user browsing session that orders the videos.
k-means cluster count k and block count b (Criteo instances) = k=100, b=144
Hand-chosen in Appendix B to construct ad categories and block-slot associations for the simulated Criteo instance.

assumptions (5)

domain assumption User behavior follows the geometric quitting-probability model: after every item or ad the user stops browsing with probability q, producing reward r_e (1-q)^{j+z(j)} for an ad at slot j.
The whole problem (Eq. 1, Problems 1-2) is defined on this model, inherited from Ieong et al. (2014); all guarantees are relative to it.
ad hoc to paper The charging identity 2 f_j(ALG_j) = sum_{j'>j} g_{j'}(1-q)^{j'-j} + sum_{e=(i,j') in ALG_j} Gamma_i holds during the execution of G-bpx.
Asserted in the proof of Theorem 5 as 'immediately implied' by the charging invariant, but not derived; the 2-approximation depends on it (Appendix A).
standard math The reward decomposition R_j = (1-q)(R_{j+1} + 1[e_{j+1} in M](r_{e_{j+1}} - q R_{j+1})) and its expansion Eq. (6).
Derived in Section 4.2 by double counting; used by Lemma 3, Lemma 4, and Theorem 5. It is a bookkeeping identity, not an empirical input.
domain assumption The prior results of Ieong et al. (2014): a PTAS for StrmAds, a 4-approximation flow algorithm, and the no-constant-online-ratio result; plus the survey claim that no better practical algorithm exists.
The 'improvement from 4 to 2' framing and the comparative claims rely on this external cited work, which the paper does not re-derive (Sections 1, 5).
standard math For StrmAds-R, the optimal choice at slot j is independent of the number z(j) of earlier ads, because (1-q)^{z(j)} is a common multiplicative factor across candidate ads.
Underlies Theorem 2's optimality proof by backward induction; the paper cites Ieong et al.'s finely-targeted-ads proof instead of a full derivation (Appendix A).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient and Practical Approximation Algorithms for Advertising in Content Feeds." pith.science (2026). https://pith.science/paper/PZLPEE5L

@misc{pith2026250202115,
  author       = {Pith},
  title        = {Pith review of: Efficient and Practical Approximation Algorithms for Advertising in Content Feeds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PZLPEE5L}},
  note         = {Machine review of arXiv:2502.02115}
}

read the original abstract

Content feeds provided by platforms such as X (formerly Twitter) and TikTok are consumed by users on a daily basis. In this paper, we revisit the native advertising problem in content feeds, initiated by Ieong et al. Given a sequence of organic items (e.g., videos or posts) relevant to a user's interests or to an information search, the goal is to place ads within the organic content so as to maximize a reward function (e.g., number of clicks), while accounting for two considerations: (1) an ad can only be inserted after a relevant content item; (2) the users' attention decays after consuming content or ads. These considerations provide a natural model for capturing both the advertisement effectiveness and the user experience. In this paper, we design fast and practical 2-approximation greedy algorithms for the associated optimization problem, improving over the best-known practical algorithm that only achieves an approximation factor of~4. Our algorithms exploit a counter-intuitive observation, namely, while top items are seemingly more important due to the decaying attention of the user, taking good care of the bottom items is key for obtaining improved approximation guarantees. We then provide the first comprehensive empirical evaluation on the problem, showing the strong empirical performance of our~methods.

Figures

Figures reproduced from arXiv: 2502.02115 by the authors.

**Figure 2.** Representation of Example 2, where a natural on [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Comparisons on synthesized bipartite graphs with [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 6.** Figure 6: Distributions of the selected slot index. [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 24 canonical work pages

[1]

Gagan Aggarwal, Jon Feldman, Shanmugavelayutham Muthukrishnan, and Mar- tin Pál. 2008. Sponsored search auctions with markovian users. In International Workshop on Internet and Network Economics . Springer, 621–628

work page 2008
[2]

Saleem Alhabash and Mengyan Ma. 2017. A Tale of Four Platforms: Motivations and Uses of Facebook, Twitter, Instagram, and Snapchat Among College Students? Social Media + Society 3, 1 (Jan. 2017). doi:10.1177/2056305117691544

work page doi:10.1177/2056305117691544 2017
[3]

Niv Buchbinder and Moran Feldman. 2018. Submodular functions maximization problems. In Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC, 753–788

work page 2018
[4]

Carlos Carrion, Zenan Wang, Harikesh Nair, Xianghong Luo, Yulin Lei, Xiliang Lin, Wenlong Chen, Qiyu Hu, Changping Peng, Yongjun Bao, et al. 2021. Blending advertising with organic content in e-commerce: A virtual bids optimization approach. arXiv preprint arXiv:2105.13556 (2021)

work page Pith review arXiv 2021
[5]

Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. 2008. An ex- perimental comparison of click position-bias models. In Proceedings of the 2008 international conference on web search and data mining . 87–94

2008
[6]

Nikhil Devanur and Aranyak Mehta. 2022. Online matching in advertisement auctions

work page 2022
[7]

eMarketer. 2024. US Native Advertising 2019. https://www.emarketer.com/ content/us-native-advertising-2019 Accessed: Oct. 2024

work page 2024
[8]

Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrish- nan, and Martin Pál. 2009. Online ad assignment with free disposal. In Interna- tional workshop on internet and network economics . Springer, 374–385

work page 2009

Show all 32 references

[9]

Iftah Gamzu and Iordanis Koutsopoulos. 2019. Advertisement allocation and mechanism design in native stream advertising. In Complex Networks and Their Applications VII: Volume 2 Proceedings The 7th International Conference on Complex Networks and Their Applications COMPLEX NET...

2019
[10]

Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. 2008. Optimal marketing strategies over social networks. In Proceedings of the 17th international conference on World Wide Web. 189–198

2008
[11]

Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. 2024. Online matching: A brief survey. arXiv preprint arXiv:2407.05381 (2024)

2024 arXiv
[12]

Samuel Ieong, Mohammad Mahdian, and Sergei Vassilvitskii. 2014. Advertising in a stream. In Proceedings of the 23rd international conference on World wide web . 29–38

2014
[13]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining . 137–146

2003
[14]

David Kempe and Mohammad Mahdian. 2008. A cascade model for externalities in sponsored search. InInternational Workshop on Internet and Network Economics. Springer, 585–596

2008
[15]

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. 1998. On syntactic versus computational views of approximability. SIAM J. Comput. 28, 1 (1998), 164–191

1998
[16]

Jon Kleinberg, Emily Ryu, and Éva Tardos. 2024. Calibrated recommendations for users with decaying attention. In International Symposium on Algorithmic Game Theory. Springer, 443–460

2024
[17]

Xuejian Li, Ze Wang, Bingqi Zhu, Fei He, Yongkang Wang, and Xingxing Wang
[18]

Guogang Liao, Ze Wang, Xiaoxu Wu, Xiaowen Shi, Chuheng Zhang, Yongkang Wang, Xingxing Wang, and Dong Wang. 2022. Cross dqn: Cross deep q network for ads allocation in feed. In Proceedings of the ACM Web Conference 2022 . 401– 409

2022
[19]

Meetanshi. 2024. 10 Native Advertising Statistics You Need to Know. https: //meetanshi.com/blog/native-advertising-statistics/ Accessed: Oct. 2024

2024
[20]

Aranyak Mehta et al. 2013. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science 8, 4 (2013), 265–368

2013
[21]

Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. 2007. Adwords and generalized online matching. Journal of the ACM (JACM) 54, 5 (2007), 22–es

2007
[22]

Silvia Milano, Mariarosaria Taddeo, and Luciano Floridi. 2020. Recommender systems and their ethical challenges. AI & SOCIETY 35, 4 (Feb. 2020), 957–967. doi:10.1007/s00146-020-00950-y

2020 doi
[23]

Outbrain. 2022. Top Native Advertising Statistics for 2022. https://www.outbrain. com/blog/native-advertising-statistics Accessed: Oct. 2024

2022
[24]

Yang Shi, Jun B Kim, and Ying Zhao. 2023. How much does ad sequence matter? Economic implications of consumer zapping and the zapping-induced externality in the television advertising market. Journal of Advertising 52, 2 (2023), 229–246

2023
[25]

Rajan Udwani. 2023. Submodular order functions and assortment optimization. In International Conference on Machine Learning . PMLR, 34584–34614

2023
[26]

Hal R Varian. 2007. Position auctions. international Journal of industrial Organi- zation 25, 6 (2007), 1163–1178

2007
[27]

David P Williamson and David B Shmoys. 2011. The design of approximation algorithms. Cambridge university press

2011
[28]

Bartosz W Wojdynski and Guy J Golan. 2016. Native advertising and the future of mass communication. American Behavioral Scientist 60, 12 (2016), 1403–1407

2016
[29]

Yizhan Wu. 2022. Submodular Order Maximization Subject to a p-Matchoid Constraint

2022
[30]

Jinyun Yan, Zhiyuan Xu, Birjodh Tiwana, and Shaunak Chatterjee. 2020. Ads allocation in feed via constrained optimization. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining . 3386– 3394

2020
[31]

ad views

Hye Jin Yoon, Yan Huang, and Mark Yi-Cheon Yim. 2023. Native advertising relevance effects and the moderating role of attitudes toward social networking sites. Journal of Research in Interactive Marketing 17, 2 (2023), 215–231. WWW ’25, April 28-May 2, 2025, Sydney, NSW, Austr...

2023
[2024]

In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval

Deep automated mechanism design for integrating ad auction and allocation in feed. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval . 1211–1220

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

Gagan Aggarwal, Jon Feldman, Shanmugavelayutham Muthukrishnan, and Mar- tin Pál. 2008. Sponsored search auctions with markovian users. In International Workshop on Internet and Network Economics . Springer, 621–628

work page 2008

[2] [2]

Saleem Alhabash and Mengyan Ma. 2017. A Tale of Four Platforms: Motivations and Uses of Facebook, Twitter, Instagram, and Snapchat Among College Students? Social Media + Society 3, 1 (Jan. 2017). doi:10.1177/2056305117691544

work page doi:10.1177/2056305117691544 2017

[3] [3]

Niv Buchbinder and Moran Feldman. 2018. Submodular functions maximization problems. In Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC, 753–788

work page 2018

[4] [4]

Carlos Carrion, Zenan Wang, Harikesh Nair, Xianghong Luo, Yulin Lei, Xiliang Lin, Wenlong Chen, Qiyu Hu, Changping Peng, Yongjun Bao, et al. 2021. Blending advertising with organic content in e-commerce: A virtual bids optimization approach. arXiv preprint arXiv:2105.13556 (2021)

work page Pith review arXiv 2021

[5] [5]

Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. 2008. An ex- perimental comparison of click position-bias models. In Proceedings of the 2008 international conference on web search and data mining . 87–94

2008

[6] [6]

Nikhil Devanur and Aranyak Mehta. 2022. Online matching in advertisement auctions

work page 2022

[7] [7]

eMarketer. 2024. US Native Advertising 2019. https://www.emarketer.com/ content/us-native-advertising-2019 Accessed: Oct. 2024

work page 2024

[8] [8]

Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrish- nan, and Martin Pál. 2009. Online ad assignment with free disposal. In Interna- tional workshop on internet and network economics . Springer, 374–385

work page 2009