Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2018 | OriginalPaper | Chapter

On Minimizing Supermodular Functions on Hereditary Systems

Authors : Victor Il’ev, Svetlana Il’eva

Published in: Optimization Problems and Their Applications

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The problem of minimizing a supermodular set function is considered. A special case of this problem is the well-known NP-hard minimization p-median problem. The main results of the paper are tight a priori and a posteriori bounds on worst-case behaviour of a “reverse” greedy (steepest descent) algorithm of minimizing a supermodular set function on comatroid. As a corollary, approximation guarantees of this algorithm for the general minimization p-median problem improving the known bounds are obtained.

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 "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

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
next chapter A New Model of Competitive Location and Pricing with the Uniform Split of the Demand
Literature
1.
Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for \(k\)-median and facility location problems. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 21–29 (2001)
2.
Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and \(k\)-median problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 378–388 (1999)
3.
Charikar, M., Guha, S., Tardos, E., Shmoys, D.B.: A constant-factor approximation algorithm for the \(k\)-median problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 1–10 (1999)
4.
Cherenin, V.P.: Solution of some combinatorial problems in optimal planning by the method of successive calculations. In: Scientific and Tutorial Proceedings of the Mathematical Economics Seminar of the Laboratory of Economic-Mathematical Methods. USSR Academy of Sciences 2, Gipromez, Moscow (1962). (in Russian)
5.
Conforti, M., Cornuéjols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3), 251–274 (1984)MathSciNetCrossRef
6.
Cornuéjols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manage. Sci. 23(8), 789–810 (1977)MathSciNetCrossRef
7.
Grötshel, M., Lovász, L.: Combinatorial optimization. In: Graham, R.L., Grötshel, M., Lovász, L. (eds.) Handbook of Combinatorics, vol. 2, pp. 1541–1598. Elsevier Science B.V, Amsterdam (1995)
8.
Il’ev, V.: An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function. Discrete Appl. Math. 114, 131–146 (2001)MathSciNetCrossRef
9.
10.
Il’ev, V., Linker, N.: On the problem of minimizing a supermodular set function on comatroid. Vestnik Omskogo Universiteta 1, 16–18 (2002). (in Russian)MATH
11.
Il’ev, V., Linker, N.: Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid. Eur. J. Oper. Res. 171, 648–660 (2006)MathSciNetCrossRef
12.
13.
Il’ev, V., Il’eva, S., Navrotskaya, A.: Approximate solution of the p-median minimization problem. Comput. Math. Math. Phys. 56(9), 1591–1597 (2016)MathSciNetCrossRef
14.
Ilev, A.V., Remeslennikov, V.N.: Study of the compatibility of systems of equations over graphs and finding their general solutions. Vestnik Omskogo Universiteta 4(86), 26–32 (2017). (in Russian)
15.
Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and \(k\)-median problems. In: 1999 Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 2–13 (1999)
16.
Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems. II. The \(p\)-medians. SIAM J. Appl. Math. 37, 539–560 (1979)MathSciNetCrossRef
17.
Kellerer, H., Strusevich, V.A.: Optimizing the half-product and related quadratic boolean functions: approximation and scheduling applications. Ann. Oper. Res. 240, 39–94 (2016)MathSciNetCrossRef
18.
Khachaturov, V.R., Khachaturov, R.V.: Supermodular programming on finite lattices. Comput. Math. Math. Phys. 52(6), 855–878 (2012)MathSciNetCrossRef
19.
Li, S., Svensson, O.: Approximating \(k\)-median via peeudo-approximation. SIAM J. Comput. 45(2), 530–547 (2013)CrossRef
20.
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)CrossRef
21.
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions - I. Math. Program. 14(13), 265–294 (1978)MathSciNetCrossRef
Metadata
Title
On Minimizing Supermodular Functions on Hereditary Systems
Authors
Victor Il’ev
Svetlana Il’eva
Copyright Year
2018
Book
Optimization Problems and Their Applications

Print ISBN: 978-3-319-93799-1

Electronic ISBN: 978-3-319-93800-4

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-93800-4_1

Premium Partner

    Image Credits