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:
Near-Optimal Asymmetric Binary Matrix Partitions Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Polynomial Kernels for Weighted Problems

Authors : Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin

Published in: Mathematical Foundations of Computer Science 2015

Publisher: Springer Berlin Heidelberg

Log in

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

search-config
loading …

Abstract

Kernelization is a formalization of efficient preprocessing for \(\mathsf {NP}\)-hard problems using the framework of parameterized complexity. Among open problems in kernelization it has been asked many times whether there are deterministic polynomial kernelizations for Subset Sum and Knapsack when parameterized by the number n of items.
We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). This result had been first used by Marx and Végh (ICALP 2013) in the context of kernelization. We further illustrate its applicability by giving polynomial kernels also for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for Subset Sum and an exponential kernelization for Knapsack. Finally, we also obtain kernelization results for polynomial integer programs.

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
previous chapter Efficient Computations over Encrypted Data Blocks
next chapter A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
Footnotes
1
This is usually called a (disjunctive) Turing kernelization.
 
Literature
1.
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)MathSciNetCrossRefMATH
2.
3.
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277–305 (2014)MathSciNetCrossRefMATH
4.
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theoret. Comput. Sci. 412(35), 4570–4578 (2011)MathSciNetCrossRefMATH
5.
Chlebík, M., Chlebíková, J.: Crown reductions for the minimum weighted vertex cover problem. Discrete Appl. Math. 156(3), 292–312 (2008)MathSciNetCrossRefMATH
6.
7.
8.
Drucker, A.: New limits to classical and quantum instance compression. In: Proceedings of the FOCS 2012, pp. 609–618 (2012)
9.
10.
11.
Fellows, M.R., Guo, J., Marx, D., Saurabh, S.: Data reduction and problem kernels (dagstuhl seminar 12241). Dagstuhl Rep. 2(6), 26–50 (2012)
12.
Frank, A., Tardos, É.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987)MathSciNetCrossRefMATH
13.
Granot, F., Skorin-Kapov, J.: On simultaneous approximation in quadratic integer programming. Oper. Res. Lett. 8(5), 251–255 (1989)MathSciNetCrossRef
14.
Harnik, D., Naor, M.: On the compressibility of \({\sf NP}\) instances and cryptographic applications. SIAM J. Comput. 39(5), 1667–1713 (2010)MathSciNetCrossRefMATH
15.
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512–530 (2001)MathSciNetCrossRefMATH
16.
Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39–49 (2013)MathSciNetCrossRefMATH
17.
18.
Kratsch, S.: On polynomial kernels for integer linear programs: covering, packing and feasibility. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 647–658. Springer, Heidelberg (2013) CrossRef
19.
20.
Marx, D., Végh, L.A.: Fixed-parameter algorithms for minimum cost edge-connectivity augmentation. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 721–732. Springer, Heidelberg (2013)
21.
Nederlof, J., van Leeuwen, E.J., van der Zwaan, R.: Reducing a target interval to a few exact queries. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 718–727. Springer, Heidelberg (2012) CrossRef
Metadata
Title
Polynomial Kernels for Weighted Problems
Authors
Michael Etscheid
Stefan Kratsch
Matthias Mnich
Heiko Röglin
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48053-3

Electronic ISBN: 978-3-662-48054-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48054-0_24

Premium Partner

    Image Credits