nach oben

Journal of Intelligent Manufacturing

Erschienen in:

24.11.2014

Uncertain programming model for uncertain minimum weight vertex covering problem

verfasst von: Lin Chen, Jin Peng, Bo Zhang, Shengguo Li

Erschienen in: Journal of Intelligent Manufacturing | Ausgabe 3/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, the minimum weight vertex covering problem with uncertain vertex weights is investigated. By virtue of the uncertainty distribution operation of independent uncertain variables, the uncertainty distribution of the minimum weight of vertex cover is derived, and the concept of the \(\alpha \)-minimum cover among uncertain weight vertex covers is proposed within the framework of uncertain programming. Then an \(\alpha \)-minimum model for uncertain weight vertex covering problem is established and discussed. Taking advantage of some properties of uncertainty theory, the model can be transformed into the corresponding deterministic form. At last, a numerical example is presented to show the performance of the model.

Vorheriger Artikel Uncertain risk aversion

Nächster Artikel Study on two-stage uncertain programming based on uncertainty theory

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bar-Yehuda, R., & Even, S. (1981). A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2, 198–203.CrossRef

Bouamama, S., Blum, C., & Boukerram, A. (2012). A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Applied Soft Computing, 12, 1632–1639.CrossRef

Feige, U., Hajiaghayi, M. T., & Lee, J. R. (2008). Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38, 629–657.CrossRef

Gao, X., Gao, Y., & Ralescu, D. A. (2010). On Liu’s inference rule for uncertain systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 18, 1–11.CrossRef

Gao, Y. (2011). Shortest path problem with uncertain arc lengths. Computers & Mathematics with Applications, 62, 2591–2600.CrossRef

Han, Q., Punnen, A. P., & Ye, Y. (2009). An edge-reduction algorithm for the vertex cover problem. Operations Research Letters, 37, 181–186.CrossRef

Han, S., Peng, Z., & Wang, S. (2014). The maximum flow problem of uncertain network. Information Sciences, 265, 167–175.CrossRef

Hartmann, A. K., & Weigt, M. (2001). Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs. Theoretical Computer Science, 265, 199–225.CrossRef

Kahneman, D., & Tversky, A. (1979). Prospect theory: An analysis of decision under risk. Econometrica, 47, 263–292.CrossRef

Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, & J. D. Bohlinger (Eds.), Complexity of Computer Computations, 85–103. New York: Plenum Press.

Kovac, P., Rodic, D., Pucovsky, V., Savkovic, B., & Gostimirovic, M. (2013). Application of fuzzy logic and regression analysis for modeling surface roughness in face milliing. Journal of Intelligent Manufacturing, 24, 755–762.CrossRef

Kratsch, S., & Neumann, F. (2013). Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65, 754–771.CrossRef

Li, X., & Liu, B. (2009). Hybrid logic and uncertain logic. Journal of Uncertain Systems, 3, 83–94.

Liu, B. (2007). Uncertainty theory (2nd ed.). Berlin: Springer-Verlag.

Liu, B. (2008). Fuzzy process, hybrid process and uncertain process. Journal of Uncertain Systems, 2, 3–16.

Liu, B. (2009a). Theory and practice of uncertain programming (2nd ed.). Berlin: Springer-Verlag.

Liu, B. (2009b). Some research problems in uncertainty theory. Journal of Uncertain Systems, 3, 3–10.

Liu, B. (2010a). Uncertainty theory: A branch of mathematics for modeling human uncertainty. Berlin: Springer-Verlag.

Liu, B. (2010b). Uncertain risk analysis and uncertain reliability analysis. Journal of Uncertain Systemsm, 4, 163–170.

Liu, B. (2012). Why is there a need for uncertainty theory? Journal of Uncertain Systems, 6, 3–10.

Liu B.,(2013) Toward uncertain finance theory, Journal of Uncertainty Analysis and Applications, 1, Article 1.

Liu, B. (2015). Uncertainty theory (4th ed.). Berlin: Springer-Verlag.

Murat, C., & Paschos, V. T. (2002). The probabilistic minimum vertex-covering problem. International Transactions in Operational Research, 9, 19–32.CrossRef

Ni, Y., Xie, L., & Liu, Z. (2010). Minimizing the expected complete influence time of a social network. Information Sciences, 180, 2514–2527.CrossRef

Ni, Y. (2012). Minimum weight covering problems in stochastic environments. Information Sciences, 214, 91–104.CrossRef

Norman, R. Z., & Rabin, M. O. (1959). An algorithm for a minimum cover of a graph. Proceedings of the American Mathematical Society, 10, 315–319.CrossRef

Oliveto, P. S., He, J., & Yao, X. (2009). Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Transactions on Evolutionary Computation, 13, 1006–1029.

Peng, Z., & Iwamura, K. (2010). A sufficient and necessary condition of uncertainty distribution. Journal of Interdisciplinary Mathematics, 13, 277–285.CrossRef

Peng, J., Zhang, B., & Li, S. (2014). Towards uncertain network optimization, Journal of Uncertainty Analysis and Applications, to be published.

Shiue, W. T. (2005). Novel state minimization and state assignment in finite state machine design for low-power portable devices. Integration, the VLSI Journal, 38, 549–570.CrossRef

Shyu, S. J., Yin, P. Y., & Lin, B. M. T. (2004). An ant colony optimization algorithm for the minimum weight vertex cover problem. Annals of Operations Research, 131, 283–304.CrossRef

Sun, G., Liu, Y. K., & Lan, Y. (2011). Fuzzy two-stage material procurement planning problem. Journal of Intelligent Manufacturing, 22, 319–331.CrossRef

Weigt, M., & Hartmann, A. K. (2000). Number of guards needed by a museum: A phase transition in vertex covering of random graphs. Physical Review Letters, 84, 6118–6121.CrossRef

Yang, X., & Gao, J. (2013). Uncertain differential games with application to capitalism, Journal of Uncertainty Analysis and Applications, 1, Article 17.

Yao, K. (2013a). Extreme values and integral of solution of uncertain differential equation, Journal of Uncertainty Analysis and Applications, 1, Article 2.

Yao, K. (2013b). A type of nonlinear uncertain differential equations with analytic solution, Journal of Uncertainty Analysis and Applications, 1, Article 8.

Zhang, B., & Peng, J. (2012). Uncertain programming model for Chinese postman problem with uncertain weights. Industrial Engineering & Management Systems, 11, 18–25.CrossRef

Zhu, Y. (2010). Uncertain optimal control with application to a portfolio selection model. Cybernetics and Systems, 41, 535–547.CrossRef

Titel: Uncertain programming model for uncertain minimum weight vertex covering problem
verfasst von: Lin Chen
Jin Peng
Bo Zhang
Shengguo Li
Publikationsdatum: 24.11.2014
Verlag: Springer US
Erschienen in: Journal of Intelligent Manufacturing / Ausgabe 3/2017
Print ISSN: 0956-5515
Elektronische ISSN: 1572-8145
DOI: https://doi.org/10.1007/s10845-014-1009-1

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2017

Bang–bang control model with optimistic value criterion for uncertain switched systems

Dynamic joint construction and optimal operation strategy of multi-period reverse logistics network: a case study of Shanghai apparel E-commerce enterprises

Uncapacitated $$p$$ p -hub location problem with fixed costs and uncertain flows

Monitoring mechanisms in new product development with risk-averse project manager

An uncertain goal programming model for machine scheduling problem

Option pricing formulas for uncertain financial market based on the exponential Ornstein–Uhlenbeck model

Premium Partner

Marktübersichten