--- _id: '2270' abstract: - lang: eng text: "Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher-\r\nent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard \ it is computationally to optimize and solve such games. One prominent such \ language is the simple yet expressive\r\nWeighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding \ the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. \ We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs." author: - first_name: Yoram full_name: Bachrach, Yoram last_name: Bachrach - first_name: Pushmeet full_name: Kohli, Pushmeet last_name: Kohli - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Morteza full_name: Zadimoghaddam, Morteza last_name: Zadimoghaddam citation: ama: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. Optimal Coalition Structures in Cooperative Graph Games. In: AAAI Press; 2013:81-87.' apa: 'Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal Coalition Structures in Cooperative Graph Games (pp. 81–87). Presented at the AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States: AAAI Press.' chicago: Bachrach, Yoram, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam. “Optimal Coalition Structures in Cooperative Graph Games,” 81–87. AAAI Press, 2013. ieee: 'Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam, “Optimal Coalition Structures in Cooperative Graph Games,” presented at the AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States, 2013, pp. 81–87.' ista: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence, 81–87.' mla: Bachrach, Yoram, et al. Optimal Coalition Structures in Cooperative Graph Games. AAAI Press, 2013, pp. 81–87. short: Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press, 2013, pp. 81–87. conference: end_date: 2013-07-18 location: Bellevue, WA, United States name: 'AAAI: Conference on Artificial Intelligence' start_date: 2013-07-14 date_created: 2018-12-11T11:56:41Z date_published: 2013-12-31T00:00:00Z date_updated: 2021-01-12T06:56:25Z day: '31' department: - _id: VlKo external_id: arxiv: - '1108.5248' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1108.5248 month: '12' oa: 1 oa_version: None page: 81-87 publication_status: published publisher: AAAI Press publist_id: '4674' quality_controlled: '1' status: public title: Optimal Coalition Structures in Cooperative Graph Games type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2273' abstract: - lang: eng text: We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results. author: - first_name: Vladimir full_name: Vladimir Kolmogorov id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Kolmogorov V. Reweighted Message Passing Revisited. IST Austria; 2013. apa: Kolmogorov, V. (2013). Reweighted message passing revisited. IST Austria. chicago: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria, 2013. ieee: V. Kolmogorov, Reweighted message passing revisited. IST Austria, 2013. ista: Kolmogorov V. 2013. Reweighted message passing revisited, IST Austria,p. mla: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria, 2013. short: V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, 2013. date_created: 2018-12-11T11:56:42Z date_published: 2013-09-22T00:00:00Z date_updated: 2019-01-24T13:07:32Z day: '22' department: - _id: VlKo extern: 0 main_file_link: - open_access: '1' url: http://arxiv.org/abs/1309.5655 month: '09' oa: 1 publication_status: published publisher: IST Austria publist_id: '4671' quality_controlled: 0 status: public title: Reweighted message passing revisited type: report year: '2013' ... --- _id: '2276' abstract: - lang: eng text: The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions. author: - first_name: Igor full_name: Gridchyn, Igor id: 4B60654C-F248-11E8-B48F-1D18A9856A87 last_name: Gridchyn - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Gridchyn I, Kolmogorov V. Potts model, parametric maxflow and k-submodular functions. In: IEEE; 2013:2320-2327. doi:10.1109/ICCV.2013.288' apa: 'Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow and k-submodular functions (pp. 2320–2327). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.288' chicago: Gridchyn, Igor, and Vladimir Kolmogorov. “Potts Model, Parametric Maxflow and k-Submodular Functions,” 2320–27. IEEE, 2013. https://doi.org/10.1109/ICCV.2013.288. ieee: 'I. Gridchyn and V. Kolmogorov, “Potts model, parametric maxflow and k-submodular functions,” presented at the ICCV: International Conference on Computer Vision, Sydney, Australia, 2013, pp. 2320–2327.' ista: 'Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular functions. ICCV: International Conference on Computer Vision, 2320–2327.' mla: Gridchyn, Igor, and Vladimir Kolmogorov. Potts Model, Parametric Maxflow and k-Submodular Functions. IEEE, 2013, pp. 2320–27, doi:10.1109/ICCV.2013.288. short: I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327. conference: end_date: 2013-12-08 location: Sydney, Australia name: 'ICCV: International Conference on Computer Vision' start_date: 2013-12-01 date_created: 2018-12-11T11:56:43Z date_published: 2013-12-01T00:00:00Z date_updated: 2021-01-12T06:56:28Z day: '01' department: - _id: JoCs - _id: VlKo doi: 10.1109/ICCV.2013.288 external_id: arxiv: - '1310.1771' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1310.1771 month: '12' oa: 1 oa_version: Preprint page: 2320 - 2327 publication_status: published publisher: IEEE publist_id: '4668' quality_controlled: '1' status: public title: Potts model, parametric maxflow and k-submodular functions type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2518' abstract: - lang: eng text: A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Živný showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities. More recently, Thapper and Živný [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard. alternative_title: - LNCS author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Kolmogorov V. The power of linear programming for finite-valued CSPs: A constructive characterization. In: Vol 7965. Springer; 2013:625-636. doi:10.1007/978-3-642-39206-1_53' apa: 'Kolmogorov, V. (2013). The power of linear programming for finite-valued CSPs: A constructive characterization (Vol. 7965, pp. 625–636). Presented at the ICALP: Automata, Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39206-1_53' chicago: 'Kolmogorov, Vladimir. “The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization,” 7965:625–36. Springer, 2013. https://doi.org/10.1007/978-3-642-39206-1_53.' ieee: 'V. Kolmogorov, “The power of linear programming for finite-valued CSPs: A constructive characterization,” presented at the ICALP: Automata, Languages and Programming, Riga, Latvia, 2013, vol. 7965, no. 1, pp. 625–636.' ista: 'Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs: A constructive characterization. ICALP: Automata, Languages and Programming, LNCS, vol. 7965, 625–636.' mla: 'Kolmogorov, Vladimir. The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization. Vol. 7965, no. 1, Springer, 2013, pp. 625–36, doi:10.1007/978-3-642-39206-1_53.' short: V. Kolmogorov, in:, Springer, 2013, pp. 625–636. conference: end_date: 2013-07-12 location: Riga, Latvia name: 'ICALP: Automata, Languages and Programming' start_date: 2013-07-08 date_created: 2018-12-11T11:58:08Z date_published: 2013-07-01T00:00:00Z date_updated: 2023-02-23T10:35:42Z day: '01' department: - _id: VlKo doi: 10.1007/978-3-642-39206-1_53 external_id: arxiv: - '1207.7213' intvolume: ' 7965' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1207.7213 month: '07' oa: 1 oa_version: Preprint page: 625 - 636 publication_status: published publisher: Springer publist_id: '4383' quality_controlled: '1' related_material: record: - id: '2271' relation: later_version status: public scopus_import: 1 status: public title: 'The power of linear programming for finite-valued CSPs: A constructive characterization' type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7965 year: '2013' ... --- _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' 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: 2021-01-12T07:00:00Z day: '02' department: - _id: VlKo doi: 10.1145/2450142.2450146 external_id: arxiv: - '1110.2809' intvolume: ' 60' 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 60 year: '2013' ...