Document

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

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.

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-dev.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

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

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.

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

Document

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

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

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-dev.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} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail