JSOM Faculty Research
Permanent URI for this communityhttps://hdl.handle.net/10735.1/2086
Browse
Browsing JSOM Faculty Research by Subject "Approximation algorithms"
Now showing 1 - 2 of 2
- Results Per Page
- Sort Options
Item Discount Allocation for Revenue Maximization in Online Social Networks(Association for Computing Machinery) Han, K.; Xu, C.; Gui, F.; Tang, Shaojie; Huang, H.; Luo, J.; Tang, ShaojieViral marketing through online social networks (OSNs) has aroused great interests in the literature. However, the fundamental problem of how to optimize the "pure gravy" of a marketing strategy through influence propagation in OSNs still remains largely open. In this paper, we consider a practical setting where the "seed nodes" in an OSN can only be probabilistically activated by the product discounts allocated to them, and make the first attempt to seek a discount allocation strategy to maximize the expected difference of profit and cost (i.e., revenue) of the strategy. We show that our problem is much harder than the conventional influence maximization issues investigated by previous work, as it can be formulated as a nonmonotone and non-submodular optimization problem. To address our problem, we propose a novel "surrogate optimization" approach as well as two randomized algorithms which can find approximation solutions with constant performance ratios with high probability. We evaluate the performance of our approach using real social networks. The extensive experimental results demonstrate that our proposed approach significantly outperforms previous work both on the revenue and on the running time.Item Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application(INFORMS) Chen, Wei; Dawande, Milind; Janakiraman, GaneshWe study fixed-dimensional stochastic dynamic programs in a discrete setting over a finite horizon. Under the primary assumption that the cost-to-go functions are discrete L♮-convex, we propose a pseudo-polynomial time approximation scheme that solves this problem to within an arbitrary prespecified additive error of ε > 0. The proposed approximation algorithm is a generalization of the explicit-enumeration algorithm and offers us full control in the trade-off between accuracy and running time. The main technique we develop for obtaining our scheme is approximation of a fixed-dimensional L♮-convex function on a bounded rectangular set, using only a selected number of points in its domain. Furthermore, we prove that the approximation function preserves L♮-convexity. Finally, to apply the approximate functions in a dynamic program, we bound the error propagation of the approximation. Our approximation scheme is illustrated on a well-known problem in inventory theory, the single-product problem with lost sales and lead times. We demonstrate the practical value of our scheme by implementing our approximation scheme and the explicit-enumeration algorithm on instances of this inventory problem.