--- _id: '1377' abstract: - lang: eng text: We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the nonconvex case and derive worst-case complexities that are equal to or better than existing methods. We show applications to total variation based two dimensional image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very effcient, offer a high degree of parallelism, and come along with memory requirements which are only in the order of the number of image pixels. author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Thomas full_name: Pock, Thomas last_name: Pock - first_name: Michal full_name: Rolinek, Michal id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87 last_name: Rolinek citation: ama: Kolmogorov V, Pock T, Rolinek M. Total variation on a tree. SIAM Journal on Imaging Sciences. 2016;9(2):605-636. doi:10.1137/15M1010257 apa: Kolmogorov, V., Pock, T., & Rolinek, M. (2016). Total variation on a tree. SIAM Journal on Imaging Sciences. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/15M1010257 chicago: Kolmogorov, Vladimir, Thomas Pock, and Michal Rolinek. “Total Variation on a Tree.” SIAM Journal on Imaging Sciences. Society for Industrial and Applied Mathematics , 2016. https://doi.org/10.1137/15M1010257. ieee: V. Kolmogorov, T. Pock, and M. Rolinek, “Total variation on a tree,” SIAM Journal on Imaging Sciences, vol. 9, no. 2. Society for Industrial and Applied Mathematics , pp. 605–636, 2016. ista: Kolmogorov V, Pock T, Rolinek M. 2016. Total variation on a tree. SIAM Journal on Imaging Sciences. 9(2), 605–636. mla: Kolmogorov, Vladimir, et al. “Total Variation on a Tree.” SIAM Journal on Imaging Sciences, vol. 9, no. 2, Society for Industrial and Applied Mathematics , 2016, pp. 605–36, doi:10.1137/15M1010257. short: V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016) 605–636. date_created: 2018-12-11T11:51:40Z date_published: 2016-05-03T00:00:00Z date_updated: 2021-01-12T06:50:15Z day: '03' department: - _id: VlKo doi: 10.1137/15M1010257 ec_funded: 1 intvolume: ' 9' issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1502.07770 month: '05' oa: 1 oa_version: Preprint page: 605 - 636 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: SIAM Journal on Imaging Sciences publication_status: published publisher: 'Society for Industrial and Applied Mathematics ' publist_id: '5834' quality_controlled: '1' scopus_import: 1 status: public title: Total variation on a tree type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9 year: '2016' ... --- _id: '1612' abstract: - lang: eng text: We prove that whenever A is a 3-conservative relational structure with only binary and unary relations,then the algebra of polymorphisms of A either has no Taylor operation (i.e.,CSP(A)is NP-complete),or it generates an SD(∧) variety (i.e.,CSP(A)has bounded width). author: - first_name: Alexandr full_name: Kazda, Alexandr id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87 last_name: Kazda citation: ama: Kazda A. CSP for binary conservative relational structures. Algebra Universalis. 2016;75(1):75-84. doi:10.1007/s00012-015-0358-8 apa: Kazda, A. (2016). CSP for binary conservative relational structures. Algebra Universalis. Springer. https://doi.org/10.1007/s00012-015-0358-8 chicago: Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” Algebra Universalis. Springer, 2016. https://doi.org/10.1007/s00012-015-0358-8. ieee: A. Kazda, “CSP for binary conservative relational structures,” Algebra Universalis, vol. 75, no. 1. Springer, pp. 75–84, 2016. ista: Kazda A. 2016. CSP for binary conservative relational structures. Algebra Universalis. 75(1), 75–84. mla: Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” Algebra Universalis, vol. 75, no. 1, Springer, 2016, pp. 75–84, doi:10.1007/s00012-015-0358-8. short: A. Kazda, Algebra Universalis 75 (2016) 75–84. date_created: 2018-12-11T11:53:01Z date_published: 2016-02-01T00:00:00Z date_updated: 2021-01-12T06:52:00Z day: '01' department: - _id: VlKo doi: 10.1007/s00012-015-0358-8 intvolume: ' 75' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1112.1099 month: '02' oa: 1 oa_version: Preprint page: 75 - 84 publication: Algebra Universalis publication_status: published publisher: Springer publist_id: '5554' quality_controlled: '1' scopus_import: 1 status: public title: CSP for binary conservative relational structures type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 75 year: '2016' ... --- _id: '1193' abstract: - lang: eng text: We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately. acknowledgement: European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160 article_number: '7782993' 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. Commutativity in the algorithmic Lovasz local lemma. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science. Vol 2016-December. IEEE; 2016. doi:10.1109/FOCS.2016.88' apa: 'Kolmogorov, V. (2016). Commutativity in the algorithmic Lovasz local lemma. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science (Vol. 2016–December). New Brunswick, NJ, USA : IEEE. https://doi.org/10.1109/FOCS.2016.88' chicago: Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, Vol. 2016–December. IEEE, 2016. https://doi.org/10.1109/FOCS.2016.88. ieee: V. Kolmogorov, “Commutativity in the algorithmic Lovasz local lemma,” in Proceedings - Annual IEEE Symposium on Foundations of Computer Science, New Brunswick, NJ, USA , 2016, vol. 2016–December. ista: 'Kolmogorov V. 2016. Commutativity in the algorithmic Lovasz local lemma. Proceedings - Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2016–December, 7782993.' mla: Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, vol. 2016–December, 7782993, IEEE, 2016, doi:10.1109/FOCS.2016.88. short: V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2016. conference: end_date: 2016-09-11 location: 'New Brunswick, NJ, USA ' name: 'FOCS: Foundations of Computer Science' start_date: 2016-09-09 date_created: 2018-12-11T11:50:38Z date_published: 2016-12-15T00:00:00Z date_updated: 2023-09-19T14:24:57Z day: '15' department: - _id: VlKo doi: 10.1109/FOCS.2016.88 ec_funded: 1 external_id: arxiv: - '1506.08547' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1506.08547v7 month: '12' oa: 1 oa_version: Preprint project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: Proceedings - Annual IEEE Symposium on Foundations of Computer Science publication_status: published publisher: IEEE publist_id: '6158' quality_controlled: '1' related_material: record: - id: '5975' relation: later_version status: public scopus_import: 1 status: public title: Commutativity in the algorithmic Lovasz local lemma type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 2016-December year: '2016' ... --- _id: '1794' abstract: - lang: eng text: We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights. acknowledgement: This work has been partially supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616160. author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Rustem full_name: Takhanov, Rustem id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87 last_name: Takhanov citation: ama: Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 2016;76(1):17-46. doi:10.1007/s00453-015-0017-7 apa: Kolmogorov, V., & Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. Springer. https://doi.org/10.1007/s00453-015-0017-7 chicago: Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica. Springer, 2016. https://doi.org/10.1007/s00453-015-0017-7. ieee: V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” Algorithmica, vol. 76, no. 1. Springer, pp. 17–46, 2016. ista: Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46. mla: Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:10.1007/s00453-015-0017-7. short: V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46. date_created: 2018-12-11T11:54:02Z date_published: 2016-09-01T00:00:00Z date_updated: 2023-10-17T09:51:31Z day: '01' department: - _id: VlKo doi: 10.1007/s00453-015-0017-7 ec_funded: 1 external_id: arxiv: - '1210.0508' intvolume: ' 76' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1210.0508 month: '09' oa: 1 oa_version: Preprint page: 17 - 46 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: Algorithmica publication_status: published publisher: Springer publist_id: '5316' quality_controlled: '1' related_material: record: - id: '2272' relation: earlier_version status: public scopus_import: 1 status: public title: Inference algorithms for pattern-based CRFs on sequence data type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 76 year: '2016' ... --- _id: '1636' abstract: - lang: eng text: "Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism R→ΓΓ between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side ΓΓ is fixed and the left side R is unconstrained.\r\n\r\nFar fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that R belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template ΓΓ (from a certain class of languages) for which the problem is tractable when R is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.\r\n\r\nAs our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs." alternative_title: - LNCS article_processing_charge: No author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Michal full_name: Rolinek, Michal id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87 last_name: Rolinek - first_name: Rustem full_name: Takhanov, Rustem last_name: Takhanov citation: ama: 'Kolmogorov V, Rolinek M, Takhanov R. Effectiveness of structural restrictions for hybrid CSPs. In: 26th International Symposium. Vol 9472. Springer Nature; 2015:566-577. doi:10.1007/978-3-662-48971-0_48' apa: 'Kolmogorov, V., Rolinek, M., & Takhanov, R. (2015). Effectiveness of structural restrictions for hybrid CSPs. In 26th International Symposium (Vol. 9472, pp. 566–577). Nagoya, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-48971-0_48' chicago: Kolmogorov, Vladimir, Michal Rolinek, and Rustem Takhanov. “Effectiveness of Structural Restrictions for Hybrid CSPs.” In 26th International Symposium, 9472:566–77. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48971-0_48. ieee: V. Kolmogorov, M. Rolinek, and R. Takhanov, “Effectiveness of structural restrictions for hybrid CSPs,” in 26th International Symposium, Nagoya, Japan, 2015, vol. 9472, pp. 566–577. ista: 'Kolmogorov V, Rolinek M, Takhanov R. 2015. Effectiveness of structural restrictions for hybrid CSPs. 26th International Symposium. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 9472, 566–577.' mla: Kolmogorov, Vladimir, et al. “Effectiveness of Structural Restrictions for Hybrid CSPs.” 26th International Symposium, vol. 9472, Springer Nature, 2015, pp. 566–77, doi:10.1007/978-3-662-48971-0_48. short: V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium, Springer Nature, 2015, pp. 566–577. conference: end_date: 2015-12-11 location: Nagoya, Japan name: 'ISAAC: International Symposium on Algorithms and Computation' start_date: 2015-12-09 date_created: 2018-12-11T11:53:10Z date_published: 2015-12-01T00:00:00Z date_updated: 2022-02-01T15:12:35Z day: '01' department: - _id: VlKo doi: 10.1007/978-3-662-48971-0_48 ec_funded: 1 external_id: arxiv: - '1504.07067' intvolume: ' 9472' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1504.07067 month: '12' oa: 1 oa_version: Preprint page: 566 - 577 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: 26th International Symposium publication_identifier: isbn: - 978-3-662-48970-3 publication_status: published publisher: Springer Nature publist_id: '5519' quality_controlled: '1' scopus_import: '1' status: public title: Effectiveness of structural restrictions for hybrid CSPs type: conference user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 volume: 9472 year: '2015' ...