Approximation Algorithms for Coordinating Ad Campaigns on Social Networks

David Kempe; Kartik Lakhotia

REVIEW 3 major objections 5 minor 38 references

Approximation Algorithms for Coordinating Ad Campaigns on Social Networks

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Shared ad campaigns: optimal revenue within factor 1/2

desk verdict Clean matroid-intersection result with a promising but currently under-proved IC rounding algorithm—worth a careful referee. read the letter →

arxiv 1908.09185 v2 pith:HECZR26M submitted 2019-08-24 cs.SI cs.GT

Kartik Lakhotia , David Kempe This is my paper · ORCID

classification cs.SIcs.GT MSC 68Q2568W2590C2791D30

keywords multi-productinfluencemaximizationsocialadvertisingsubmodularmatroidintersectionreversereachabilitydependentroundingIndependentCascademodelapproximationalgorithms

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

The paper asks how a social network should place sponsored ads for many paying advertisers when no user should be exposed to too many sponsored ads. It claims that, under the general threshold model with monotone submodular local influence functions, this coordination problem reduces to monotone submodular maximization over the intersection of two matroids, and therefore admits constant-factor polynomial-time approximation algorithms. It then specializes to the Independent Cascade model, where combining reverse-reachable sets with LP rounding yields a more practical $1-1/e$ approximation, with advertiser budgets enforced in expectation. A careful reader would care because the reduction turns an awkward multi-party constraint problem into standard optimization machinery, and the experiments map when competition between advertisers is most costly.

What carries the argument

The argument's load-bearing construction is a lifted network with one copy $u_{v,j}$ for each advertiser $j$ and node $v$. Choosing a subset of these copies is equivalent to choosing seed sets for all advertisers; the per-user exposure cap $r_v$ becomes a partition matroid on the copies $X_v$, and the per-advertiser caps $K^{(j)}$ together with the total seed cap $K$ become another partition matroid (truncated when needed) on the copies $U^{(j)}$. Submodularity of influence in the general threshold model makes the revenue functions submodular, so the whole problem becomes a known optimization task. For the Independent Cascade case, a second mechanism carries the practical algorithm: random reverse-reachable sets (the sets of nodes that can reach a randomly sampled target through the random live-edge graph) estimate influence as a maximum-coverage objective, and a dependent-rounding scheme turns the resulting LP solution into integral seed choices while preserving marginals and negative correlation.

What would settle it

Find a small Independent Cascade instance, for instance the star network from the paper's integrality-gap construction, and run the proposed LP-rounding repeatedly. Measure, for one reverse-reachable set $R_i$, the probability that no seed lands in $R_i$ and compare it with the product of the individual probabilities that each node in $R_i$ is left unseeded. If the former ever exceeds the latter, the negative-correlation step in the proof of the $1-1/e$ claim is false, and that claim must be weakened.

Watch

Extended reading notes

Core claim

The central claim is that coordinating several ad campaigns on one network, under per-user sponsored-ad exposure caps and advertiser seed-set limits, reduces to maximizing a nonnegative, monotone, submodular function subject to the intersection of two matroids; without per-advertiser seed caps, the feasible region collapses to a single truncated partition matroid. Because the resulting revenue functions are submodular, known approximation algorithms apply: a local-search algorithm gives essentially $1/2$ for the two-matroid case, continuous greedy gives $1-1/e$ for the single-matroid case, and simple greedy gives $1/2$. For the Independent Cascade model, the paper contributes a more efficient $1-1/e$ algorithm based on random reverse-reachable sets and dependent LP rounding, with the caveat that advertiser budgets are only guaranteed in expectation. The paper also establishes experimentally that competition reduces host revenue most when advertiser influence networks are similar and when tie strengths are intermediate.

Load-bearing premise

The Independent Cascade $1-1/e$ guarantee depends on the assumption that the final rounding step enforcing the total seed budget does not destroy the rounding's negative-correlation property; if that property fails, the guarantee does not follow, while the matroid-based results remain unaffected.

Editorial extensions

If this is right

A platform with arbitrary per-user ad caps and per-advertiser seed caps can coordinate any number of campaigns in polynomial time while keeping at least half of the optimal revenue; with only per-user caps, it can reach $1-1/e$.
The reduction is modular: any future improvement to submodular maximization under matroid intersection automatically improves coordinated ad campaigns, including versions with different costs for targeting seed nodes.
Under the Independent Cascade model, campaigns on networks of tens of thousands of nodes can be computed with a $1-1/e$ guarantee, though a single run may exceed an advertiser's budget; budgets hold on average across runs.
Experiments imply that the host's revenue loss from competition is predictable from network similarity and tie strength: similar influence networks and intermediate tie strengths produce the worst losses.

Reading between the lines

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

The clean matroid reduction suggests that the experimental competition loss could be quantified as a normalized submodularity gap, and the swap-based similarity experiments could be converted into a predictor: measure the overlap of high-influence neighborhoods across advertisers and compare it with the observed payoff ratio.
The star-graph integrality gap indicates that exact per-run advertiser budgets are qualitatively harder than expected budgets; a natural testable extension is a post-processing step that swaps seeds to restore budget caps and measures how much of the $1-1/e$ guarantee survives.
Because the paper's IC proof assumes an extension of dependent rounding whose negative-correlation property is not proved, an immediate empirical check is to compare the rounding's observed coverage probability against the lower bound used in the proof on random IC instances; if the inequality fails, that guarantee would need repair while the matroid results stand.
If the similarity experiments generalize, platforms could choose which advertisers to co-schedule: advertisers with highly overlapping influential users should be scheduled separately, while those with disjoint influence neighborhoods can share a campaign wave.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Here's the short version: the Section 3 result is the real contribution and it's clean. Theorem 6's proof, as written, is not clean—there's a missing factor and an unproved extension—but neither issue looks fatal.

Section 3 recasts the multi-advertiser problem as monotone submodular maximization over the intersection of two matroids. That explicit reduction is new for this problem and it immediately improves the guarantees from Datta et al. (1/3) and Tang-Yuan (1/4) to essentially 1/2, and 1-1/e when per-advertiser seed caps are dropped. The argument uses standard building blocks and I see no circularity. This is a useful result worth citing.

The IC LP-rounding algorithm in Section 4 is a good idea and the experiments are reasonable, but the proof of Theorem 6 has two problems. First, ŷ(j) is defined without the n/ρ factor from LP constraint (5), so the claimed E[ŷ(j)] ≥ (1-1/e)y(j) doesn't follow as written. That's a straightforward fix. Second, the extension of Gandhi et al. rounding to the global seed budget is asserted in a footnote, not proved. The stress-test concern about negative correlation is partly over-stated—after the standard rounding, each advertiser/node has at most one fractional variable, so the final loop mostly pairs variables from different constraints and the product inequality is likely preserved—but the paper doesn't show this, and the proof leans on it at step (1). A referee should ask for a full proof or a citeable version.

The experiments are fine for what they are, but no code or seeds are provided, so I'd treat the empirical conclusions as illustrative. The observation about intermediate tie strengths is worth reporting.

Bottom line: this deserves serious refereeing. The matroid part is solid, and the IC algorithm is likely fixable into a correct (1-1/e) guarantee. I'd engage with it and would cite the Section 3 reduction.

Referee Report

3 major / 5 minor

Summary. The paper studies coordinated advertising campaigns on a social network, where multiple advertisers run independent influence cascades but compete for per-node exposure caps and, optionally, per-advertiser seed set budgets. The host maximizes either expected revenue W or revenue based on expected exposure \bar W. The main theoretical contribution is a reduction, under the general threshold model with monotone submodular local influence functions, of the multi-product influence maximization problem to monotone submodular maximization over a matroid intersection: with per-advertiser seed caps the feasible region is the intersection of two matroids, giving a (1/(2+\epsilon))-approximation, and without seed caps it is a single truncated partition matroid, giving a (1-1/e-\epsilon)-approximation via continuous greedy. For the Independent Cascade model, the paper proposes an LP based on reverse reachable sets, rounded using the dependent rounding algorithm of Gandhi et al., and claims a (1-1/e)-approximation with budgets enforced in expectation. Experiments on four real networks compare greedy and LP-rounding algorithms, study the effect of network similarity and tie strength on competition, and report scalability results for a parallel greedy algorithm.

Significance. The Section 3 reduction is a genuinely useful conceptual contribution: it makes the matroid structure of multi-advertiser constraints explicit, subsumes earlier models of Datta et al. and Aslay et al., and immediately imports known approximation algorithms, improving the previous 1/3 guarantee to essentially 1/2 in the two-matroid case and 1-1/e in the single-matroid case. The reverse-reachability LP-rounding algorithm, if its proof is repaired, would be a practically attractive method for IC networks of tens of thousands of nodes, and the paper's experiments provide useful qualitative evidence about how competition reduces host revenue. The main weakness is that the proof of the headline IC result, Theorem 6, has load-bearing gaps that are not merely cosmetic.

major comments (3)

[Section 4.2, definition of \hat y(j) and Theorem 6 proof] The proof of Theorem 6 compares E[\hat y(j)] with y(j), but \hat y(j) is defined immediately before the theorem as \hat y(j)=\sum_{i\in R(j)} \gamma(j)\hat x_i, omitting the factor n/\rho that appears in LP constraint (5). Since y(j)\le (n/\rho)\sum_{i\in R(j)}\gamma(j)x_i, the final chain of inequalities yields only E[\hat y(j)]\ge (1-1/e)(\rho/n)y(j), not the claimed E[\hat y(j)]\ge (1-1/e)y(j). The proof should redefine \hat y(j) with the n/\rho scaling and then handle the cap \min(B(j), \gamma(j)E[N_j]) explicitly for the expected-exposure objective.
[Section 4.2, final-loop extension of Gandhi et al.] The proposed extension of dependent rounding to enforce the global seed budget \sum_{j,v} z_v^{(j)}\le K is not a consequence of the Gandhi et al. framework and, as described, does not produce a feasible solution with probability 1. Pairwise rounding of arbitrary fractional variables can overshoot the total: three fractional variables of value 0.3 belonging to three different advertisers have fractional total 0.9, yet the described final loop, which pairs them and then rounds the last variable alone, produces a rounded total of 2 with positive probability even when K=1. Thus the claim that all ILP constraints except the budget cap are satisfied is unsupported. Moreover, the negative-correlation inequality (1) used in Theorem 6 requires that for each advertiser j and each RR set R_i, the all-zero event on the variables {z_v^{(j)}: v\in R_i} is negatively correlated; Gandhi et al. guarantee this property for subsets of edges incident to a common node of the original bipartite graph, and no proof is given that the final loop preserves it. This is a load-bearing step for the (1-1/e) IC guarantee.
[Section 4.1, payoff estimation error, second case] The proof states that when B(j)\le \gamma(j), any nonempty S(j) yields \gamma(j)q(j)\ge B(j) 'with probability 1'. This is false: q(j)=n\cdot|\{i\in R(j): R_i\cap S(j)\neq\emptyset\}|/\rho is a random RR-set estimate and can be 0 with positive probability even for a nonempty S(j). The error bound should instead be argued under the high-probability event from Lemma 5, where q(j)\ge 1-\epsilon/m; this can still give an O(\epsilon) total estimation error, but the argument as written needs to be corrected.

minor comments (5)

[Abstract] The abstract contains a typo: 'orgain' should be 'organic'.
[Section 4.2] The notation in the LP constraint \sum_{v\in R_i} z_v^{(j(i))} is ambiguous, because R_i is defined as a subset of the cloned universe U^{(j)}, while z is indexed by original network nodes v; the authors should state explicitly that the sum is over original nodes whose copies appear in R_i.
[Section 5.3] In the description of the node-swap process, 'performs· n/100 node swaps' should read 'performs s· n/100 node swaps'.
[Theorem 6] The theorem statement should make explicit that the guarantee holds with high probability over the random RR-set sampling, and, in the budgeted case, in expectation over the rounding; the current statement reads as a deterministic worst-case guarantee, which the proof does not provide.
[Section 4.2, proof of Theorem 6] The step from E[\hat y(j)]\ge (1-1/e)y(j) to an approximation guarantee for the expected-exposure revenue with the cap min(B(j),\cdot) is omitted; the authors should spell out the inequality E[\min(B,cX)]\ge (1-1/e)\min(B,cE[X]) for nonnegative X.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main claims are derived from external submodular-maximization and rounding theorems, and self-citations are background only.

full rationale

The paper's central result is an explicit reduction of Multi-Product Influence Maximization to monotone submodular maximization subject to matroid constraints. Section 3 constructs the disjoint union graph \hat{G}, identifies the per-advertiser seed caps with a partition matroid on the sets U^(j), and the per-node exposure caps together with the global seed cap with a truncated partition matroid on the sets X_v. Submodularity of the influence objective is imported from Mossel and Roch [28], and the approximation guarantees are imported from Lee et al. [24], Fisher et al. [14], and Vondrák [6,35]. These are external mathematical results, not definitions of the paper's own outputs, and no parameter is fitted to data and then renamed a prediction. The Section 4 LP-rounding algorithm for the Independent Cascade model likewise relies on the external Reverse Reachability results of Borgs et al. and Tang et al., and on Gandhi et al.'s dependent rounding theorem; the proof's negative-correlation step is stated as a property of that external rounding algorithm. The self-citations [21] and [22] are background: [22] supplies the standard general-threshold/IC model and the live-edge equivalence, and [21] is a related-competition reference, but neither is used as the load-bearing support for the new approximation claims. No uniqueness theorem by the present authors is invoked to forbid alternatives, and no ansatz is smuggled in through a self-citation. One technical concern is worth flagging but is not circularity: the footnote before Theorem 6 says 'We extend the rounding algorithm of Gandhi et al. by one more final loop' for the global seed budget, and Theorem 6's step (1) requires that the negative-correlation inequality survive that extension, which the paper does not prove. In addition, the definition of \hat{y}^{(j)} just before Theorem 6 omits the n/ρ factor appearing in LP constraint (5), so the displayed inequality E[\hat{y}^{(j)}] ≥ (1-1/e)y^{(j)} appears to need an additional factor or a different definition. These are unproved technical steps in the strongest algorithmic claim, but they are gaps in proof rather than reductions of a prediction to its input by construction; the general Section 3 results are independent of them. Accordingly, the circularity score is 0.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The theoretical guarantees rest on standard external theorems, including Mossel-Roch, matroid truncation, Lee et al., Vondrák, Fisher et al., Gandhi et al., and Tang et al. The only ad hoc technical assumption is the unproved final-loop extension of dependent rounding to the total seed budget. Experimental parameters, such as ρ=10n and λ_v ranges, are hand-chosen but do not enter the theoretical claims.

free parameters (2)

rho(j): number of reverse reachable sets per advertiser = 10n in experiments
Chosen empirically in Appendix B to keep estimation error around 2%; the theoretical bound in Section 4.1 is much larger and impractical. This parameter is hand-tuned and affects all experimental numbers, but it does not enter the theoretical approximation claims.
lambda_v ranges for synthetic edge probabilities = [0,0.4] for Facebook, DBLP, NetHEPT; [0,0.3] for Advogato
Chosen by hand to compensate for varying edge densities; affects the synthetic influence networks and all reported revenue values.

assumptions (7)

standard math Mossel-Roch theorem: under the general threshold model with monotone submodular local influence functions and independent thresholds, the expected influence as a function of the seed set is monotone submodular.
Invoked in Section 3 to establish submodularity of W and \bar W; theorem from reference [28].
standard math A truncation of a matroid is again a matroid, so partition matroids with capacities K(j) or r_v combined with a total cardinality bound K remain matroids.
Used in the reduction in Section 3 to argue the constraints form one or two matroids; the definition appears in Appendix A.1.
standard math Known approximation theorems: Lee et al. local search for k matroids gives 1/(k+ε); Vondrák continuous greedy for one matroid gives 1-1/e-ε; Fisher et al. greedy gives 1/(k+1); Gandhi et al. dependent rounding provides marginal preservation and negative correlation.
These external results carry the approximation guarantees in Sections 3 and 4.
standard math Tang et al. Lemma 5 concentration bound for reverse reachable sets.
Used in Section 4.1 to guarantee simultaneous accurate estimation of influence for all relevant seed sets.
ad hoc to paper The extension of Gandhi et al. dependent rounding with a final loop to enforce the total seed budget preserves marginals and negative correlation.
Asserted without proof in Section 4.2; the proof of Theorem 6 relies on it. This is the weakest technical step.
domain assumption Advertisers' diffusions are independent except for shared seed constraints; node activation for different products does not interfere.
Stated in Section 2; the additive objective, a sum over advertisers, depends on this. If ads compete for user adoption, the problem changes.
domain assumption Value functions w(j) are monotone submodular, or concave in cardinality, and local influence functions are monotone submodular.
Assumed from Section 2; submodularity and the approximation guarantees depend on these.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Approximation Algorithms for Coordinating Ad Campaigns on Social Networks." pith.science (2026). https://pith.science/paper/HECZR26M

@misc{pith2026190809185,
  author       = {Pith},
  title        = {Pith review of: Approximation Algorithms for Coordinating Ad Campaigns on Social Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HECZR26M}},
  note         = {Machine review of arXiv:1908.09185}
}

read the original abstract

We study a natural model of coordinated social ad campaigns over a social network, based on models of Datta et al. and Aslay et al. Multiple advertisers are willing to pay the host - up to a known budget - per user exposure, whether the exposure is sponsored or orgain (i.e. shared by a friend). Campaigns are seeded with sponsored ads to some users, but no user must be exposed to too many sponsored ads. Thus, while ad campaigns proceed independently over the network, they need to be carefully coordinated with respect to their seed sets. We study the objective of maximizing host's total ad revenue. Our main result is to show that under a broad class of influence models, the problem can be reduced to maximizing a submodular function subject to two matroid constraints; it can therefore be approximated within a factor essentially 1/2 in polynomial time. When there is no bound on the individual seed set sizes of advertisers, the constraints correspond only to a single matroid, and the guarantee can be improved to 1-1/e; in that case, a factor 1/2 is achieved by a practical greedy algorithm. The 1-1/e approximation algorithm for matroid-constrained problem is far from practical; however, we show that specifically under the Independent Cascade model, LP rounding and Reverse Reachability techniques can be combined to obtain a 1-1/e approximation algorithm. Our theoretical results are complemented by experiments evaluating the extent to which the coordination of multiple ad campaigns inhibits the revenue obtained from each individual campaign, as a function of the similarity of the influence networks and strength of ties in the networks. Our experiments suggest that as networks for different advertisers become less similar, the harmful effect of competition decreases. With respect to tie strengths, we show that the most harm is done in an intermediate range.

Figures

Figures reproduced from arXiv: 1908.09185 by the authors.

**Figure 2.** Average per-advertiser payoff vs. number of advertisers ( [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

**Figure 3.** Host payoff vs. influence network similarity. [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: Relative payoff with m = 20 advertisers vs. influence probability p (shown in non-linear scale to display interesting regimes) be different. Advogato has a high edge density; as a result, advertisements spread to a large portion of the graph even for small p; in partic…

**Figure 5.** Figure 5: Running times of the sequential and parallel Greedy algorithm on the [PITH_FULL_IMAGE:figures/full_fig_p020_5.png]

**Figure 6.** Figure 6: Absolute error in payoff estimation for different numbers of RR sets and advertisers [PITH_FULL_IMAGE:figures/full_fig_p026_6.png]

**Figure 7.** Figure 7: Standard deviation of the estimated payoff, normalized by the mean, for different numbers [PITH_FULL_IMAGE:figures/full_fig_p027_7.png]

**Figure 8.** Figure 8: Average payoff of selected seed set normalized by the payoff of seed set obtained with very [PITH_FULL_IMAGE:figures/full_fig_p027_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

[1]

Helping local businesses reach more customers.https://www.facebook.com/business/news/ facebook-local-awareness, 2014

work page 2014
[2]

https://www.wordstream.com/blog/ws/2018/01/25/ hyperlocal-marketing, 2018

Hyperlocal advertising. https://www.wordstream.com/blog/ws/2018/01/25/ hyperlocal-marketing, 2018. 21

work page 2018
[3]

Viral mar- keting meets social advertising: Ad allocation with minimum regret.Proc

Cigdem Aslay, Wei Lu, Francesco Bonchi, Amit Goyal, and Laks VS Lakshmanan. Viral mar- keting meets social advertising: Ad allocation with minimum regret.Proc. VLDB Endowment, 8(7):814–825, 2015

work page 2015
[4]

Maximizing social inﬂuence in nearly optimal time

Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social inﬂuence in nearly optimal time. InProc. 25th ACM-SIAM Symp. on Discrete Algorithms, pages 946–957, 2014

work page 2014
[5]

Maximizing a submodular set function subject to a matroid constraint

Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. InProc. 12th Intel. Conf. on Integer Programming and Combinatorial Optimization, pages 182–196, 2007

work page 2007
[6]

Maximizing a submodular set function subject to a matroid constraint.SIAM Journal on Computing, 40(6):1740–1766, 2011

Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint.SIAM Journal on Computing, 40(6):1740–1766, 2011

work page 2011
[7]

Submodular function maximization via the multilinear relaxation and contention resolution schemes

Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. InProc. 43rd ACM Symp. on Theory of Computing, pages 783–792, 2011

work page 2011
[8]

Lakshmanan, and Carlos Castillo.Information and Inﬂuence Propagation in Social Networks

Wei Chen, Laks V.S. Lakshmanan, and Carlos Castillo.Information and Inﬂuence Propagation in Social Networks. Synthesis Lectures on Data Management. Morgan & Claypool, 2013

work page 2013

Show all 38 references

[9]

Eﬃcient inﬂuence maximization in social networks

Wei Chen, Yajun Wang, and Siyu Yang. Eﬃcient inﬂuence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199–208. ACM, 2009

2009
[10]

Scalable inﬂuence maximization in social networks under the linear threshold model

Wei Chen, Yifei Yuan, and Li Zhang. Scalable inﬂuence maximization in social networks under the linear threshold model. InProc. 10th Intl. Conf. on Data Mining, pages 88–97, 2010

2010
[11]

Viral marketing for multiple products

Samik Datta, Anirban Majumder, and Nisheeth Shrivastava. Viral marketing for multiple products. In Proc. 10th Intl. Conf. on Data Mining, pages 118–127, 2010

2010
[12]

Mining the network value of customers

Pedro Domingos and Matthew Richardson. Mining the network value of customers. InProc. 7th Intl. Conf. on Knowledge Discovery and Data Mining, pages 57–66, 2001

2001
[13]

Competing for customers in a social network: The quasi-linear case

Pradeep Dubey, Rahul Garg, and Bernard de Meyer. Competing for customers in a social network: The quasi-linear case. InProc. 2nd Workshop on Internet and Network Economics (WINE), pages 162–173, 2006

2006
[14]

Fisher, George L

Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey. An analysis of approx- imations for maximizing submodular set functions — ii. Mathematical Programming Study, 8:73–87, 1978

1978
[15]

Dependent rounding and its applications to approximation algorithms.Journal of the ACM, 53(3):324–360, 2006

Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms.Journal of the ACM, 53(3):324–360, 2006

2006
[16]

Talk of the network: A complex systems look at the underlying process of word-of-mouth.Marketing Letters, 12:211–223, 2001

Jacob Goldenberg, Barak Libai, and Eitan Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth.Marketing Letters, 12:211–223, 2001. 22

2001
[17]

Jacob Goldenberg, Barak Libai, and Eitan Muller. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity eﬀects on new product growth through stochastic cellular automata.Academy of Marketing Science Review, 9:1, 2001

2001
[18]

Competitive contagion in networks

Sanjeev Goyal and Michael Kearns. Competitive contagion in networks. InProc. 44th ACM Symp. on Theory of Computing, pages 759–774, 2012

2012
[19]

An eﬃcient linear programming based method for the inﬂuence maximization problem in social networks.Information Sciences, 503:589–605, 2019

Evren Güney. An eﬃcient linear programming based method for the inﬂuence maximization problem in social networks.Information Sciences, 503:589–605, 2019

2019
[20]

Hartline, Vahab S

Jason D. Hartline, Vahab S. Mirrokni, and Mukund Sundararajan. Optimal marketing strate- gies over social networks. In17th Intl. World Wide Web Conference, pages 189–198, 2008

2008
[21]

Price of anarchy for then-player competitive cascade game with submodular activation functions

Xinran He and David Kempe. Price of anarchy for then-player competitive cascade game with submodular activation functions. In Proc. 9th Conference on Web and Internet Economics (WINE), pages 232–248, 2013

2013
[22]

Maximizing the spread of inﬂuence in a social network

David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of inﬂuence in a social network. Theory of Computing, 11(4):105–147, 2015

2015
[23]

Konect: the koblenz network collection

Jérôme Kunegis. Konect: the koblenz network collection. In 22nd Intl. World Wide Web Conference, pages 1343–1350, 2013

2013
[24]

Submodular maximization over multiple ma- troids via generalized exchange properties

Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple ma- troids via generalized exchange properties. In Proc. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 244–257, 2009

2009
[25]

Lehmann, and Noam Nisan

Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270–296, 2006

2006
[26]

Shuyang Lin, Qingbo Hu, Fengjiao Wang, and Philip S. Yu. Steering information diﬀusion dynamically against user attention limitation. InProc. 14th Intl. Conf. on Data Mining, pages 330–339. IEEE Computer Society, 2014

2014
[27]

Wei Lu, Wei Chen, and Laks V. S. Lakshmanan. From competition to complementarity: Comparative inﬂuence diﬀusion and maximization.Proc. VLDB Endowment, 9(2):60–71, 2015

2015
[28]

Submodularity of inﬂuence in social networks: From local to global.SIAM Journal on Computing, 39(6):2176–2188, 2010

Elchanan Mossel and Sebastien Roch. Submodularity of inﬂuence in social networks: From local to global.SIAM Journal on Computing, 39(6):2176–2188, 2010

2010
[29]

Submodular maximization by simulated annealing

Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms, pages 1098–1116, 2011

2011
[30]

Oxley.Matroid Theory

James G. Oxley.Matroid Theory. Oxford University Press, 1992

1992
[31]

Optimizing ad allocation in social advertising

Shaojie Tang and Jing Yuan. Optimizing ad allocation in social advertising. InProceedings of the 25th ACM International on Conference on Information and Knowledge Management, pages 1383–1392. ACM, 2016

2016
[32]

Inﬂuence maximization in near-linear time: A martingale approach

Youze Tang, Yanchen Shi, and Xiaokui Xiao. Inﬂuence maximization in near-linear time: A martingale approach. InProc. 34th ACM SIGMOD Intl. Conference on Management of Data, pages 1539–1554, 2015. 23

2015
[33]

Inﬂuence maximization: near-optimal time complexity meets practical eﬃciency

Youze Tang, Xiaokui Xiao, and Yanchen Shi. Inﬂuence maximization: near-optimal time complexity meets practical eﬃciency. InProc. 33rd ACM SIGMOD Intl. Conference on Man- agement of Data, pages 75–86, 2014

2014
[34]

Digital advertising attitudes report

Upstream and YouGov. Digital advertising attitudes report. http://cache-www. upstreamsystems.com/wp-content/uploads/2014/02/yougov12_report.pdf, 2012

2014
[35]

Optimal approximation for the submodular welfare problem in the value oracle model

Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. 40th ACM Symp. on Theory of Computing, pages 67–74, 2008

2008
[36]

Symmetry and approximability of submodular maximization problems

Jan Vondrák. Symmetry and approximability of submodular maximization problems. InProc. 50th IEEE Symp. on Foundations of Computer Science, pages 651–670, 2009

2009
[37]

Scalable inﬂuence maximization for independent cascade model in large-scale social networks.Data Mining and Knowledge Discovery Journal, 25(3):545–576, 2012

Chi Wang, Wei Chen, and Yajun Wang. Scalable inﬂuence maximization for independent cascade model in large-scale social networks.Data Mining and Knowledge Discovery Journal, 25(3):545–576, 2012

2012
[38]

End-to-end inﬂuence maximization in the ﬁeld

Bryan Wilder, Laura Onasch-Vera, Juliana Hudson, Jose Luna, Nicole Wilson, Robin Petering, Darlene Woo, Milind Tambe, and Eric Rice. End-to-end inﬂuence maximization in the ﬁeld. In Proc. 17th Intl. Conf. on Autonomous Agents and Multiagent Systems, pages 1414–1422, 2018. 24 A...

2018

Pith tools

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

[1] [1]

Helping local businesses reach more customers.https://www.facebook.com/business/news/ facebook-local-awareness, 2014

work page 2014

[2] [2]

https://www.wordstream.com/blog/ws/2018/01/25/ hyperlocal-marketing, 2018

Hyperlocal advertising. https://www.wordstream.com/blog/ws/2018/01/25/ hyperlocal-marketing, 2018. 21

work page 2018

[3] [3]

Viral mar- keting meets social advertising: Ad allocation with minimum regret.Proc

Cigdem Aslay, Wei Lu, Francesco Bonchi, Amit Goyal, and Laks VS Lakshmanan. Viral mar- keting meets social advertising: Ad allocation with minimum regret.Proc. VLDB Endowment, 8(7):814–825, 2015

work page 2015

[4] [4]

Maximizing social inﬂuence in nearly optimal time

Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social inﬂuence in nearly optimal time. InProc. 25th ACM-SIAM Symp. on Discrete Algorithms, pages 946–957, 2014

work page 2014

[5] [5]

Maximizing a submodular set function subject to a matroid constraint

Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. InProc. 12th Intel. Conf. on Integer Programming and Combinatorial Optimization, pages 182–196, 2007

work page 2007

[6] [6]

Maximizing a submodular set function subject to a matroid constraint.SIAM Journal on Computing, 40(6):1740–1766, 2011

Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint.SIAM Journal on Computing, 40(6):1740–1766, 2011

work page 2011

[7] [7]

Submodular function maximization via the multilinear relaxation and contention resolution schemes

Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. InProc. 43rd ACM Symp. on Theory of Computing, pages 783–792, 2011

work page 2011

[8] [8]

Lakshmanan, and Carlos Castillo.Information and Inﬂuence Propagation in Social Networks

Wei Chen, Laks V.S. Lakshmanan, and Carlos Castillo.Information and Inﬂuence Propagation in Social Networks. Synthesis Lectures on Data Management. Morgan & Claypool, 2013

work page 2013