KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Fri, 23 Jun 2017 11:37:27 +0200Fri, 23 Jun 2017 11:37:27 +0200Product Pricing with Additive Influences - Algorithms and Complexity Results for Pricing in Social Networks
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4662
We introduce and investigate a product pricing model in social networks where the value a possible buyer assigns to a product is influenced by the previous buyers. The selling proceeds in discrete, synchronous rounds for some set price and the individual values are additively altered. Whereas computing the revenue for a given price can be done in polynomial time, we show that the basic problem PPAI, i.e., is there a price generating a requested revenue, is weakly NP-complete. With algorithm Frag we provide a pseudo-polynomial time algorithm checking the range of prices in intervals of common buying behavior we call fragments. In some special cases, e.g., solely positive influences, graphs with bounded in-degree, or graphs with bounded path length, the amount of fragments is polynomial. Since the run-time of Frag is polynomial in the amount of fragments, the algorithm itself is polynomial for these special cases. For graphs with positive influence we show that every buyer does also buy for lower prices, a property that is not inherent for arbitrary graphs. Algorithm FixHighest improves the run-time on these graphs by using the above property.
Furthermore, we introduce variations on this basic model. The version of delaying the propagation of influences and the awareness of the product can be implemented in our basic model by substituting nodes and arcs with simple gadgets. In the chapter on Dynamic Product Pricing we allow price changes, thereby raising the complexity even for graphs with solely positive or negative influences. Concerning Perishable Product Pricing, i.e., the selling of products that are usable for some time and can be rebought afterward, the principal problem is computing the revenue that a given price can generate in some time horizon. In general, the problem is #P-hard and algorithm Break runs in pseudo-polynomial time. For polynomially computable revenue, we investigate once more the complexity to find the best price.
We conclude the thesis with short results in topics of Cooperative Pricing, Initial Value as Parameter, Two Product Pricing, and Bounded Additive Influence. Florian David Schwahndoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4662Fri, 23 Jun 2017 11:37:27 +0200Polyhedral Analysis of Hub Center Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1851
A hub location problem consists of locating p hubs in a network in order to collect and consolidate flow between node pairs. This thesis deals with the uncapacitated single allocation p-hub center problem (USApHCP) as a special type of hub location problem with min max objective function. Using the so-called radius formulation of the problem, the dimension of the polyhedron of USApHCP is derived. The formulation constraints are investigated to find out which of these define facets. Then, three new classes of facet-defining inequalities are derived. Finally, efficient procedures to separate facets in a branch-and-cut algorithm are proposed. The polyhedral analysis of USApHCP is based on a tight relation to the uncapacitated facility location problem (UFL). Hence, many results stated in this thesis also hold for UFL.Silke Baumgartnerdiplomhttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1851Wed, 11 Apr 2007 10:46:01 +0200