---
_id: '2828'
abstract:
- lang: eng
text: 'We study the complexity of valued constraint satisfaction problems (VCSPs)
parametrized by a constraint language, a fixed set of cost functions over a finite
domain. An instance of the problem is specified by a sum of cost functions from
the language and the goal is to minimize the sum. Under the unique games conjecture,
the approximability of finite-valued VCSPs is well understood, see Raghavendra
[2008]. However, there is no characterization of finite-valued VCSPs, let alone
general-valued VCSPs, that can be solved exactly in polynomial time, thus giving
insights from a combinatorial optimization perspective. We consider the case of
languages containing all possible unary cost functions. In the case of languages
consisting of only {0, ∞}-valued cost functions (i.e., relations), such languages
have been called conservative and studied by Bulatov [2003, 2011] and recently
by Barto [2011]. Since we study valued languages, we call a language conservative
if it contains all finite-valued unary cost functions. The computational complexity
of conservative valued languages has been studied by Cohen et al. [2006] for languages
over Boolean domains, by Deineko et al. [2008] for {0, 1}-valued languages (a.k.a
Max-CSP), and by Takhanov [2010a] for {0, ∞}-valued languages containing all finite-valued
unary cost functions (a.k.a. Min-Cost-Hom). We prove a Schaefer-like dichotomy
theorem for conservative valued languages: if all cost functions in the language
satisfy a certain condition (specified by a complementary combination of STP and
MJN multimor-phisms), then any instance can be solved in polynomial time (via
a new algorithm developed in this article), otherwise the language is NP-hard.
This is the first complete complexity classification of general-valued constraint
languages over non-Boolean domains. It is a common phenomenon that complexity
classifications of problems over non-Boolean domains are significantly harder
than the Boolean cases. The polynomial-time algorithm we present for the tractable
cases is a generalization of the submodular minimization problem and a result
of Cohen et al. [2008]. Our results generalize previous results by Takhanov [2010a]
and (a subset of results) by Cohen et al. [2006] and Deineko et al. [2008]. Moreover,
our results do not rely on any computer-assisted search as in Deineko et al. [2008],
and provide a powerful tool for proving hardness of finite-valued and general-valued
languages.'
article_number: '10'
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Stanislav
full_name: Živný, Stanislav
last_name: Živný
citation:
ama: Kolmogorov V, Živný S. The complexity of conservative valued CSPs. Journal
of the ACM. 2013;60(2). doi:10.1145/2450142.2450146
apa: Kolmogorov, V., & Živný, S. (2013). The complexity of conservative valued
CSPs. Journal of the ACM. ACM. https://doi.org/10.1145/2450142.2450146
chicago: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative
Valued CSPs.” Journal of the ACM. ACM, 2013. https://doi.org/10.1145/2450142.2450146.
ieee: V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,”
Journal of the ACM, vol. 60, no. 2. ACM, 2013.
ista: Kolmogorov V, Živný S. 2013. The complexity of conservative valued CSPs. Journal
of the ACM. 60(2), 10.
mla: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative
Valued CSPs.” Journal of the ACM, vol. 60, no. 2, 10, ACM, 2013, doi:10.1145/2450142.2450146.
short: V. Kolmogorov, S. Živný, Journal of the ACM 60 (2013).
date_created: 2018-12-11T11:59:48Z
date_published: 2013-04-02T00:00:00Z
date_updated: 2025-09-29T13:52:07Z
day: '02'
department:
- _id: VlKo
doi: 10.1145/2450142.2450146
external_id:
arxiv:
- '1110.2809'
isi:
- '000318628500004'
fulldoi: https://doi.org/10.1145/2450142.2450146
intvolume: ' 60'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1110.2809
month: '04'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '3971'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity of conservative valued CSPs
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 60
year: '2013'
...
---
_id: '2901'
abstract:
- lang: eng
text: ' We introduce the M-modes problem for graphical models: predicting the M
label configurations of highest probability that are at the same time local maxima
of the probability landscape. M-modes have multiple possible applications: because
they are intrinsically diverse, they provide a principled alternative to non-maximum
suppression techniques for structured prediction, they can act as codebook vectors
for quantizing the configuration space, or they can form component centers for
mixture model approximation. We present two algorithms for solving the M-modes
problem. The first algorithm solves the problem in polynomial time when the underlying
graphical model is a simple chain. The second algorithm solves the problem for
junction chains. In synthetic and real dataset, we demonstrate how M-modes can
improve the performance of prediction. We also use the generated modes as a tool
to understand the topography of the probability distribution of configurations,
for example with relation to the training set size and amount of noise in the
data. '
alternative_title:
- PMLR
article_processing_charge: No
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Zhu
full_name: Yan, Zhu
last_name: Yan
- first_name: Dimitris
full_name: Metaxas, Dimitris
last_name: Metaxas
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable
modes of a graphical model. In: Proceedings of the 16th International Conference
on Artificial Intelligence and Statistics. Vol 31. Journal of Machine Learning
Research; 2013:161-169.'
apa: 'Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013).
Computing the M most probable modes of a graphical model. In Proceedings of
the 16th International Conference on Artificial Intelligence and Statistics
(Vol. 31, pp. 161–169). Scottsdale, AZ, United States: Journal of Machine Learning
Research.'
chicago: Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph
Lampert. “Computing the M Most Probable Modes of a Graphical Model.” In Proceedings
of the 16th International Conference on Artificial Intelligence and Statistics,
31:161–69. Journal of Machine Learning Research, 2013.
ieee: C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the
M most probable modes of a graphical model,” in Proceedings of the 16th International
Conference on Artificial Intelligence and Statistics, Scottsdale, AZ, United
States, 2013, vol. 31, pp. 161–169.
ista: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M
most probable modes of a graphical model. Proceedings of the 16th International
Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Uncertainty
in Artificial Intelligence, PMLR, vol. 31, 161–169.'
mla: Chen, Chao, et al. “Computing the M Most Probable Modes of a Graphical Model.”
Proceedings of the 16th International Conference on Artificial Intelligence
and Statistics, vol. 31, Journal of Machine Learning Research, 2013, pp. 161–69.
short: C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, Proceedings
of the 16th International Conference on Artificial Intelligence and Statistics,
Journal of Machine Learning Research, 2013, pp. 161–169.
conference:
end_date: 2013-05-01
location: Scottsdale, AZ, United States
name: 'AISTATS: Conference on Uncertainty in Artificial Intelligence'
start_date: 2013-04-29
das_tickbox: '1'
date_created: 2018-12-11T12:00:14Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2026-07-06T13:43:58Z
day: '01'
department:
- _id: HeEd
- _id: VlKo
- _id: ChLa
intvolume: ' 31'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://jmlr.org/proceedings/papers/v31/chen13a.html
month: '01'
oa: 1
oa_version: None
page: 161 - 169
publication: Proceedings of the 16th International Conference on Artificial Intelligence
and Statistics
publication_status: published
publisher: Journal of Machine Learning Research
publist_id: '3846'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing the M most probable modes of a graphical model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2013'
...
---
_id: '2928'
abstract:
- lang: eng
text: ' This paper addresses the problem of approximate MAP-MRF inference in
general graphical models. Following [36], we consider a family of linear programming
relaxations of the problem where each relaxation is specified by a set of nested
pairs of factors for which the marginalization constraint needs to be enforced.
We develop a generalization of the TRW-S algorithm [9] for this problem, where
we use a decomposition into junction chains, monotonic w.r.t. some ordering on
the nodes. This generalizes the monotonic chains in [9] in a natural way. We also
show how to deal with nested factors in an efficient way. Experiments show an
improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on
a number of computer vision and natural language processing problems. '
article_number: '1205.6352'
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Thomas
full_name: Schoenemann, Thomas
last_name: Schoenemann
citation:
ama: Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message
passing. arXiv. doi:10.48550/arXiv.1205.6352
apa: Kolmogorov, V., & Schoenemann, T. (n.d.). Generalized sequential tree-reweighted
message passing. arXiv. https://doi.org/10.48550/arXiv.1205.6352
chicago: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted
Message Passing.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1205.6352.
ieee: V. Kolmogorov and T. Schoenemann, “Generalized sequential tree-reweighted
message passing,” arXiv. .
ista: Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message
passing. arXiv, 1205.6352.
mla: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted
Message Passing.” ArXiv, 1205.6352, doi:10.48550/arXiv.1205.6352.
short: V. Kolmogorov, T. Schoenemann, ArXiv (n.d.).
corr_author: '1'
date_created: 2018-12-11T12:00:23Z
date_published: 2012-05-29T00:00:00Z
date_updated: 2025-07-08T07:19:42Z
day: '29'
department:
- _id: VlKo
doi: 10.48550/arXiv.1205.6352
external_id:
arxiv:
- '1205.6352'
fulldoi: https://doi.org/10.48550/arXiv.1205.6352
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1205.6352
month: '05'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
publist_id: '3809'
status: public
title: Generalized sequential tree-reweighted message passing
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2930'
abstract:
- lang: eng
text: "In this paper we investigate k-submodular functions. This natural family
of discrete functions includes submodular and bisubmodular functions as the special
cases k = 1 and k = 2 respectively.\r\n\r\nIn particular we generalize the known
Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts
that the minimum of the (bi)submodular function can be found by solving a maximization
problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron,
prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm
to construct the vertices of the polyhedron.\r\n"
acknowledgement: "We would like to thank Andrei Krokhin for encourag- ing our cooperation,
for helpful discussions, and for his critical reading of the manuscript.\r\n"
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Anna
full_name: Huber, Anna
last_name: Huber
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Huber A, Kolmogorov V. Towards minimizing k-submodular functions. In: Vol
7422. Springer; 2012:451-462. doi:10.1007/978-3-642-32147-4_40'
apa: 'Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions
(Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial
Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40'
chicago: Huber, Anna, and Vladimir Kolmogorov. “Towards Minimizing K-Submodular
Functions,” 7422:451–62. Springer, 2012. https://doi.org/10.1007/978-3-642-32147-4_40.
ieee: 'A. Huber and V. Kolmogorov, “Towards minimizing k-submodular functions,”
presented at the ISCO: International Symposium on Combinatorial Optimization,
Athens, Greece, 2012, vol. 7422, pp. 451–462.'
ista: 'Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO:
International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.'
mla: Huber, Anna, and Vladimir Kolmogorov. Towards Minimizing K-Submodular Functions.
Vol. 7422, Springer, 2012, pp. 451–62, doi:10.1007/978-3-642-32147-4_40.
short: A. Huber, V. Kolmogorov, in:, Springer, 2012, pp. 451–462.
conference:
end_date: 2012-04-21
location: Athens, Greece
name: 'ISCO: International Symposium on Combinatorial Optimization'
start_date: 2012-04-19
date_created: 2018-12-11T12:00:24Z
date_published: 2012-04-01T00:00:00Z
date_updated: 2025-06-11T08:08:15Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-642-32147-4_40
external_id:
arxiv:
- '1309.5469'
fulldoi: https://doi.org/10.1007/978-3-642-32147-4_40
intvolume: ' 7422'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5469
month: '04'
oa: 1
oa_version: Preprint
page: 451 - 462
publication_status: published
publisher: Springer
publist_id: '3806'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Towards minimizing k-submodular functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7422
year: '2012'
...
---
_id: '2931'
abstract:
- lang: eng
text: "In this paper, we present a new approach for establishing correspondences
between sparse image features related by an unknown nonrigid mapping and corrupted
by clutter and occlusion, such as points extracted from images of different instances
of the same object category. We formulate this matching task as an energy minimization
problem by defining an elaborate objective function of the appearance and the
spatial arrangement of the features. Optimization of this energy is an instance
of graph matching, which is in general an NP-hard problem. We describe a novel
graph matching optimization technique, which we refer to as dual decomposition
(DD), and demonstrate on a variety of examples that this method outperforms existing
graph matching algorithms. In the majority of our examples, DD is able to find
the global minimum within a minute. The ability to globally optimize the objective
allows us to accurately learn the parameters of our matching model from training
examples. We show on several matching tasks that our learned model yields results
superior to those of state-of-the-art methods.\r\n"
acknowledgement: This research was funded in part by Microsoft Research.
article_processing_charge: No
author:
- first_name: Lorenzo
full_name: Torresani, Lorenzo
last_name: Torresani
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
citation:
ama: Torresani L, Kolmogorov V, Rother C. A dual decomposition approach to feature
correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence.
2012;35(2):259-271. doi:10.1109/TPAMI.2012.105
apa: Torresani, L., Kolmogorov, V., & Rother, C. (2012). A dual decomposition
approach to feature correspondence. IEEE Transactions on Pattern Analysis and
Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2012.105
chicago: Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “A Dual Decomposition
Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis
and Machine Intelligence. IEEE, 2012. https://doi.org/10.1109/TPAMI.2012.105.
ieee: L. Torresani, V. Kolmogorov, and C. Rother, “A dual decomposition approach
to feature correspondence,” IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 35, no. 2. IEEE, pp. 259–271, 2012.
ista: Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to
feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence.
35(2), 259–271.
mla: Torresani, Lorenzo, et al. “A Dual Decomposition Approach to Feature Correspondence.”
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35,
no. 2, IEEE, 2012, pp. 259–71, doi:10.1109/TPAMI.2012.105.
short: L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis
and Machine Intelligence 35 (2012) 259–271.
date_created: 2018-12-11T12:00:24Z
date_published: 2012-05-08T00:00:00Z
date_updated: 2025-09-30T08:15:06Z
day: '08'
department:
- _id: VlKo
doi: 10.1109/TPAMI.2012.105
external_id:
isi:
- '000312560600002'
fulldoi: https://doi.org/10.1109/TPAMI.2012.105
intvolume: ' 35'
isi: 1
issue: '2'
language:
- iso: eng
month: '05'
oa_version: None
page: 259 - 271
project:
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_status: published
publisher: IEEE
publist_id: '3805'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A dual decomposition approach to feature correspondence
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 35
year: '2012'
...
---
_id: '5396'
abstract:
- lang: eng
text: We consider the problem of inference in agraphical model with binary variables.
While in theory it is arguably preferable to compute marginal probabilities, in
practice researchers often use MAP inference due to the availability of efficient
discrete optimization algorithms. We bridge the gap between the two approaches
by introducing the Discrete Marginals technique in which approximate marginals
are obtained by minimizing an objective function with unary and pair-wise terms
over a discretized domain. This allows the use of techniques originally devel-oped
for MAP-MRF inference and learning. We explore two ways to set up the objective
function - by discretizing the Bethe free energy and by learning it from training
data. Experimental results show that for certain types of graphs a learned function
can out-perform the Bethe approximation. We also establish a link between the
Bethe free energy and submodular functions.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Filip
full_name: Korc, Filip
id: 476A2FD6-F248-11E8-B48F-1D18A9856A87
last_name: Korc
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Korc F, Kolmogorov V, Lampert C. Approximating Marginals Using Discrete
Energy Minimization. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003
apa: Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003
chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating
Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003.
ieee: F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete
energy minimization. IST Austria, 2012.
ista: Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
energy minimization, IST Austria, 13p.
mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization.
IST Austria, 2012, doi:10.15479/AT:IST-2012-0003.
short: F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete
Energy Minimization, IST Austria, 2012.
date_created: 2018-12-12T11:39:06Z
date_published: 2012-07-23T00:00:00Z
date_updated: 2024-10-09T20:54:48Z
day: '23'
ddc:
- '000'
department:
- _id: VlKo
- _id: ChLa
doi: 10.15479/AT:IST-2012-0003
file:
- access_level: open_access
checksum: 7e0ba85ad123b13223aaf6cdde2d288c
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:29Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5490'
file_name: IST-2012-0003_IST-2012-0003.pdf
file_size: 618744
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
fulldoi: https://doi.org/10.15479/AT:IST-2012-0003
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '13'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '36'
related_material:
record:
- id: '3124'
relation: earlier_version
status: public
status: public
title: Approximating marginals using discrete energy minimization
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '3117'
abstract:
- lang: eng
text: We consider the problem of minimizing a function represented as a sum of submodular
terms. We assume each term allows an efficient computation of exchange capacities.
This holds, for example, for terms depending on a small number of variables, or
for certain cardinality-dependent terms. A naive application of submodular minimization
algorithms would not exploit the existence of specialized exchange capacity subroutines
for individual terms. To overcome this, we cast the problem as a submodular flow
(SF) problem in an auxiliary graph in such a way that applying most existing SF
algorithms would rely only on these subroutines. We then explore in more detail
Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular,
we show how to improve its complexity in the case when the function contains cardinality-dependent
terms.
article_processing_charge: No
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Minimizing a sum of submodular functions. Discrete Applied
Mathematics. 2012;160(15):2246-2258. doi:10.1016/j.dam.2012.05.025
apa: Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete
Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2012.05.025
chicago: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete
Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2012.05.025.
ieee: V. Kolmogorov, “Minimizing a sum of submodular functions,” Discrete Applied
Mathematics, vol. 160, no. 15. Elsevier, pp. 2246–2258, 2012.
ista: Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied
Mathematics. 160(15), 2246–2258.
mla: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete
Applied Mathematics, vol. 160, no. 15, Elsevier, 2012, pp. 2246–58, doi:10.1016/j.dam.2012.05.025.
short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258.
corr_author: '1'
date_created: 2018-12-11T12:01:29Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2025-09-30T08:01:04Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2012.05.025
external_id:
isi:
- '000308052600017'
fulldoi: https://doi.org/10.1016/j.dam.2012.05.025
intvolume: ' 160'
isi: 1
issue: '15'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1006.1990
month: '10'
oa: 1
oa_version: Preprint
page: 2246 - 2258
publication: Discrete Applied Mathematics
publication_status: published
publisher: Elsevier
publist_id: '3582'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Minimizing a sum of submodular functions
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 160
year: '2012'
...
---
_id: '3124'
abstract:
- lang: eng
text: "We consider the problem of inference in a graphical model with binary variables.
While in theory it is arguably preferable to compute marginal probabilities, in
practice researchers often use MAP inference due to the availability of efficient
discrete optimization algorithms. We bridge the gap between the two approaches
by introducing the Discrete Marginals technique in which approximate marginals
are obtained by minimizing an objective function with unary and pairwise terms
over a discretized domain. This allows the use of techniques originally developed
for MAP-MRF inference and learning. We explore two ways to set up the objective
function - by discretizing the Bethe free energy and by learning it from training
data. Experimental results show that for certain types of graphs a learned function
can outperform the Bethe approximation. We also establish a link between the Bethe
free energy and submodular functions.\r\n"
alternative_title:
- Inferning 2012
author:
- first_name: Filip
full_name: Korc, Filip
id: 476A2FD6-F248-11E8-B48F-1D18A9856A87
last_name: Korc
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy
minimization. In: ICML; 2012.'
apa: 'Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
using discrete energy minimization. Presented at the ICML: International Conference
on Machine Learning, Edinburgh, Scotland: ICML.'
chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating
Marginals Using Discrete Energy Minimization.” ICML, 2012.
ieee: 'F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete
energy minimization,” presented at the ICML: International Conference on Machine
Learning, Edinburgh, Scotland, 2012.'
ista: 'Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
energy minimization. ICML: International Conference on Machine Learning, Inferning
2012, .'
mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization.
ICML, 2012.
short: F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.
conference:
end_date: 2012-07-01
location: Edinburgh, Scotland
name: 'ICML: International Conference on Machine Learning'
start_date: 2012-06-26
corr_author: '1'
date_created: 2018-12-11T12:01:31Z
date_published: 2012-06-30T00:00:00Z
date_updated: 2024-10-09T20:54:48Z
day: '30'
ddc:
- '000'
department:
- _id: ChLa
- _id: VlKo
file:
- access_level: open_access
checksum: 3d0d4246548c736857302aadb2ff5d15
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:34Z
date_updated: 2020-07-14T12:46:00Z
file_id: '4889'
file_name: IST-2016-565-v1+1_DM-inferning2012.pdf
file_size: 305836
relation: main_file
file_date_updated: 2020-07-14T12:46:00Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
publication_status: published
publisher: ICML
publist_id: '3575'
pubrep_id: '565'
quality_controlled: '1'
related_material:
record:
- id: '5396'
relation: later_version
status: public
status: public
title: Approximating marginals using discrete energy minimization
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '3257'
abstract:
- lang: eng
text: Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that
the relaxation is totally half-integral if f̂(x) is a polyhedral function with
half-integral extreme points x, and this property is preserved after adding an
arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ
where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation
for quadratic pseudo-Boolean functions f. We argue that total half-integrality
is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean
functions. Our contributions are as follows. First, we provide a complete characterization
of totally half-integral relaxations f̂ by establishing a one-to-one correspondence
with bisubmodular functions. Second, we give a new characterization of bisubmodular
functions. Finally, we show some relationships between general totally half-integral
relaxations and relaxations based on the roof duality. On the conceptual level,
our results show that bisubmodular functions provide a natural generalization
of the roof duality approach to higher-order terms. This can be viewed as a non-submodular
analogue of the fact that submodular functions generalize the s-t minimum cut
problem with non-negative weights to higher-order terms.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete
Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026
apa: Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions.
Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026
chicago: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026.
ieee: V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete
Applied Mathematics, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012.
ista: Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete
Applied Mathematics. 160(4–5), 416–426.
mla: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26,
doi:10.1016/j.dam.2011.10.026.
short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.
corr_author: '1'
date_created: 2018-12-11T12:02:18Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2025-09-30T07:43:17Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2011.10.026
external_id:
arxiv:
- '1005.2305'
isi:
- '000301211100006'
fulldoi: https://doi.org/10.1016/j.dam.2011.10.026
intvolume: ' 160'
isi: 1
issue: 4-5
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1005.2305
month: '03'
oa: 1
oa_version: Preprint
page: 416 - 426
publication: Discrete Applied Mathematics
publication_status: published
publisher: Elsevier
publist_id: '3397'
quality_controlled: '1'
related_material:
record:
- id: '2934'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Generalized roof duality and bisubmodular functions
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 160
year: '2012'
...