1 Search Results for "Moriguchi, Satoko"


Document
Scaling and Proximity Properties of Integrally Convex Functions

Authors: Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, and Fabio Tardella

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)


Abstract
In discrete convex analysis, the scaling and proximity properties for the class of L^natural-convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when n leq 2, while a proximity theorem can be established for any n, but only with an exponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discretely convex function in one dimension to the case of integrally convex functions in two dimensions. Furthermore, we identified a new class of discrete convex functions, called directed integrally convex functions, which is strictly between the classes of L^natural -convex and integrally convex functions but enjoys the same scaling and proximity properties that hold for L^natural -convex functions.

Cite as

Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, and Fabio Tardella. Scaling and Proximity Properties of Integrally Convex Functions. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 57:1-57:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{moriguchi_et_al:LIPIcs.ISAAC.2016.57,
  author =	{Moriguchi, Satoko and Murota, Kazuo and Tamura, Akihisa and Tardella, Fabio},
  title =	{{Scaling and Proximity Properties of Integrally Convex Functions}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{57:1--57:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.57},
  URN =		{urn:nbn:de:0030-drops-68368},
  doi =		{10.4230/LIPIcs.ISAAC.2016.57},
  annote =	{Keywords: Discrete optimization, discrete convexity, proximity theorem, scaling algorithm}
}
  • Refine by Author
  • 1 Moriguchi, Satoko
  • 1 Murota, Kazuo
  • 1 Tamura, Akihisa
  • 1 Tardella, Fabio

  • Refine by Classification

  • Refine by Keyword
  • 1 Discrete optimization
  • 1 discrete convexity
  • 1 proximity theorem
  • 1 scaling algorithm

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail