90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
- 90-00 General reference works (handbooks, dictionaries, bibliographies, etc.)
- 90-01 Instructional exposition (textbooks, tutorial papers, etc.)
- 90-02 Research exposition (monographs, survey articles)
- 90-03 Historical (must also be assigned at least one classification number from Section 01)
- 90-04 Explicit machine computation and programs (not the theory of computation or programming)
- 90-06 Proceedings, conferences, collections, etc.
- 90-08 Computational methods
-
90Bxx Operations research and management science
(4)
-
90Cxx Mathematical programming [See also 49Mxx, 65Kxx]
(24)
Filtern
Dokumenttyp
- Diplomarbeit (1)
- Dissertation (1)
Schlagworte
- Hub-and-Spoke-System (1)
- Polyhedron (1)
-
Product Pricing with Additive Influences - Algorithms and Complexity Results for Pricing in Social Networks
(2017)
- 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.
-
Polyhedral Analysis of Hub Center Problems
(2003)
- 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.
