Top

Journal of Combinatorial Optimization

Published in:

27-09-2020

Partial inverse min–max spanning tree problem

Authors: Javad Tayyebi, Ali Reza Sepasian

Published in: Journal of Combinatorial Optimization | Issue 4/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper addresses a partial inverse combinatorial optimization problem, called the partial inverse min–max spanning tree problem. For a given weighted graph G and a forest F of the graph, the problem is to modify weights at minimum cost so that a bottleneck (min–max) spanning tree of G contains the forest. In this paper, the modifications are measured by the weighted Manhattan distance. The main contribution is to present two algorithms to solve the problem in polynomial time. This result is considerable because the partial inverse minimum spanning tree problem, which is closely related to this problem, is proved to be NP-hard in the literature. Since both the algorithms have the same worse-case complexity, some computational experiments are reported to compare their running time.

previous article An approximation algorithm for submodular hitting set problem with linear penalties

next article Maximizing user type diversity for task assignment in crowdsourcing

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

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!

inform now

Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, USAMATH

Ahuja RK, Orlin JB (2000) A faster algorithm for the inverse spanning tree problem. J Algorithms 34(1):177–193MathSciNetMATHCrossRef

Ahuja RK, Orlin JB (2001) Inverse optimization. Oper Res 49(5):771–783MathSciNetMATHCrossRef

Babier A, Boutilier JJ, Sharpe MB, McNiven AL, Chan TC (2018) Inverse optimization of objective function weights for treatment planning using clinical dose-volume histograms. Phys Med Biol 63(10):105004CrossRef

Bard JF (1991) Some properties of the bilevel programming problem. J Optim Theory Appl 68(2):371–378MathSciNetMATHCrossRef

Birge JR, Hortaçsu A, Pavlin JM (2017) Inverse optimization for the recovery of market structure from market outcomes: an application to the miso electricity market. Oper Res 65(4):837–855MathSciNetMATHCrossRef

Cai MC, Duin CW, Yang X, Zhang J (2008) The partial inverse minimum spanning tree problem when weight increase is forbidden. Eur J Oper Res 188(2):348–353MathSciNetMATHCrossRef

Camerini PM (1978) The min–max spanning tree problem and some extensions. Inf Process Lett 7(1):10–14MathSciNetMATHCrossRef

Chan TC, Lee T (2018) Trade-off preservation in inverse multi-objective convex optimization. Eur J Oper Res 270(1):25–39MathSciNetMATHCrossRef

Demange M, Monnot J (2010) An introduction to inverse combinatorial problems. In: Paschos VT (ed) Paradigms of combinatorial optimization (problems and new approaches). ISTE-WILEY, London-Hoboken (UK-USA), pp 547–586MATH

DeNegre ST, Ralphs TK (2009) A branch-and-cut algorithm for integer bilevel linear programs. In: Chinneck JW, Kristjansson B, Saltzman MJ (eds) Operations research and cyber-infrastructure. Springer, Boston, pp 65–78CrossRef

Erdõs P, Rényi A (1976) On the evolution of random graphs. Sel Pap Alfréd Rényi 2:482–525

Gentry S (2001) Partial inverse linear programming, MIT Lab for information and decision systems report, LIDS-P-2532, Dec

Ghobadi K, Lee T, Mahmoudzadeh H, Terekhov D (2018) Robust inverse optimization. Oper Res Lett 46(3):339–344MathSciNetMATHCrossRef

Guan X, Pardalos PM, Zuo X (2015) Inverse Max\(+\)Sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) Norm. J Glob Optim 61(1):165–182MathSciNetMATH

Hartmann T, Wagner D (2012) Fast and simple fully-dynamic cut tree construction. In: International symposium on algorithms and computation. Springer, Berlin, pp 95–105

He Y, Zhang B, Yao E (2005) Weighted inverse minimum spanning tree problems under Hamming distance. J Comb Optim 9(1):91–100MathSciNetMATHCrossRef

Heuberger C (2004) Inverse combinatorial optimization: A survey on problems, methods, and results. J Comb Optim 8(3):329–361MathSciNetMATHCrossRef

Hochbaum DS (2003) Efficient algorithms for the inverse spanning-tree problem. Oper Res 51(5):785–797MathSciNetMATHCrossRef

Lai TC, Orlin JB (2003). The complexity of preprocessing. Research report of Sloan School of Mangement

Li X, Zhang Z, Du DZ (2018) Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm. J Glob Optim 70(3):677–685MATH

Liu L, Yao E (2007) Inverse min–max spanning tree problem under the weighted sum-type Hamming distance. In: Chen B, Paterson M, Zhang G (eds) Combinatorics, algorithms, probabilistic and experimental methodologies. Springer, Berlin, pp 375–383CrossRef

Liu L, Wang Q (2009) Constrained inverse min–max spanning tree problems under the weighted Hamming distance. J Glob Optim 43(1):83–95MathSciNetMATHCrossRef

Magnanti TL, Wolsey LA (1995) Optimal trees. In: Birge J, Linetsky V (eds) Handbooks in operations research and management science, vol 7. Elsevier, Amsterdam, pp 503–615

Pop PC (2019) The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances. Eur J Oper Res. https://doi.org/10.1016/j.ejor.2019.05.017MATHCrossRef

Saez-Gallego J, Morales JM (2018) Short-term forecasting of price-responsive loads using inverse optimization. IEEE Trans Smart Grid 9(5):4805–4814CrossRef

Sleator DD, Tarjan RE (1983) A data structure for dynamic trees. J Comput Syst Sci 26(3):362–391MathSciNetMATHCrossRef

Sokkalingam PT, Ahuja RK, Orlin JB (1996) Inverse spanning tree problems: formulations and algorithms, Working Paper #3890-96, MIT Sloan School of Management

Tarantola A (2005) Inverse problem theory and methods for model parameter estimation, vol 89. SIAM, New DelhiMATHCrossRef

Yang C, Zhang J (1998) Inverse maximum capacity problems. Oper Res Spektrum 20(2):97–100MathSciNetMATHCrossRef

Zeng B, An Y (2014) Solving bilevel mixed integer program by reformulations and decomposition. http://www.optimizationonline.org/DB_FILE/2014/07/4455.pdf. Accessed 20 Aug 2016

Zhang J, Liu Z, Ma Z (1996) On the inverse problem of minimum spanning tree with partition constraints. Math Methods Oper Res 44(2):171–187MathSciNetMATHCrossRef

Zhang J, Xu S, Ma Z (1997) An algorithm for inverse minimum spanning tree problem. Optim Methods Softw 8(1):69–84MathSciNetMATHCrossRef

Zhang B, Zhang J, He Y (2006) Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance. J Glob Optim 34(3):467–474MathSciNetMATHCrossRef

Title: Partial inverse min–max spanning tree problem
Authors: Javad Tayyebi
Ali Reza Sepasian
Publication date: 27-09-2020
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 4/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00656-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2020

New approximation algorithms for machine scheduling with rejection on single and parallel machine

Intersecting families in

Some algorithmic results for finding compatible spanning circuits in edge-colored graphs

A characterization of optimal multiprocessor schedules and new dominance rules

Online maximum matching with recourse

A short proof for stronger version of DS decomposition in set function optimization

Premium Partner