Search Results

Documents authored by Murota, Kazuo

Document
DOI: 10.4230/LIPIcs.STACS.2018.39
Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection

Authors: Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Zivny

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions.An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper-Zivny classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa-Murota-Zivny made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.
Cite as

Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Zivny. Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hirai_et_al:LIPIcs.STACS.2018.39,
  author =	{Hirai, Hiroshi and Iwamasa, Yuni and Murota, Kazuo and Zivny, Stanislav},
  title =	{{Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.39},
  URN =		{urn:nbn:de:0030-drops-85042},
  doi =		{10.4230/LIPIcs.STACS.2018.39},
  annote =	{Keywords: valued constraint satisfaction problems, discrete convex analysis, M-convexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.57
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.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}
}
Document
DOI: 10.4230/DagSemProc.05011.10
Fundamentals in Discrete Convex Analysis

Authors: Kazuo Murota

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
This talk describes fundamental properties of M-convex and L-convex functions that play the central roles in discrete convex analysis. These concepts were originally introduced in combinatorial optimization, but turned out to be relevant in economics. Emphasis is put on discrete duality and conjugacy respect to the Legendre-Fenchel transformation. Monograph information: http://www.misojiro.t.u-tokyo.ac.jp/~murota/mybooks.html#DCAsiam2003
Cite as

Kazuo Murota. Fundamentals in Discrete Convex Analysis. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{murota:DagSemProc.05011.10,
  author =	{Murota, Kazuo},
  title =	{{Fundamentals in Discrete Convex Analysis}},
  booktitle =	{Computing and Markets},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.10},
  URN =		{urn:nbn:de:0030-drops-2167},
  doi =		{10.4230/DagSemProc.05011.10},
  annote =	{Keywords: gross substitute, discrete convex functions, M-convex function, Fenchel-Legendre transformation}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact