TY - CONF
AB - We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations.
AU - Kuske, Jan
AU - Swoboda, Paul
AU - Petra, Stefanie
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 646
SN - 978-331958770-7
TI - A novel convex relaxation for non binary discrete tomography
VL - 10302
ER -
TY - CONF
AB - We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.
AU - Swoboda, Paul
AU - Andres, Bjoern
ID - 915
SN - 978-153860457-1
TI - A message passing algorithm for the minimum cost multicut problem
VL - 2017
ER -
TY - CONF
AB - We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.
AU - Swoboda, Paul
AU - Rother, Carsten
AU - Abu Alhaija, Carsten
AU - Kainmueller, Dagmar
AU - Savchynskyy, Bogdan
ID - 916
SN - 978-153860457-1
TI - A study of lagrangean decompositions and dual ascent solvers for graph matching
VL - 2017
ER -
TY - CONF
AB - We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.
AU - Swoboda, Paul
AU - Kuske, Jan
AU - Savchynskyy, Bogdan
ID - 917
SN - 978-153860457-1
TI - A dual ascent framework for Lagrangean decomposition of combinatorial problems
VL - 2017
ER -
TY - THES
AB - An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of
variables, a finite domain of labels, and a set of constraints, each constraint acting on
a subset of the variables. The goal is to find an assignment of labels to its variables
that satisfies all constraints (or decide whether one exists). If we allow more general
“soft” constraints, which come with (possibly infinite) costs of particular assignments,
we obtain instances from a richer class called Valued Constraint Satisfaction Problem
(VCSP). There the goal is to find an assignment with minimum total cost.
In this thesis, we focus (assuming that P
6
=
NP) on classifying computational com-
plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core
content of the work. In one of them, we consider VCSPs parametrized by a constraint
language, that is the set of “soft” constraints allowed to form the instances, and finish
the complexity classification modulo (missing pieces of) complexity classification for
analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect
matching algorithm. This generalization contributes to complexity classfications in two
ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean
CSPs in which every variable may appear in at most two constraints and second, it
settles full classification of Boolean CSPs with planar drawing (again parametrized by a
constraint language).
AU - Rolinek, Michal
ID - 992
TI - Complexity of constraint satisfaction
ER -
TY - CONF
AB - The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 1192
SN - 978-161197478-2
TI - Even delta-matroids and the complexity of planar Boolean CSPs
ER -
TY - DATA
AB - Small synthetic discrete tomography problems.
Sizes are 32x32, 64z64 and 256x256.
Projection angles are 2, 4, and 6.
Number of labels are 3 and 5.
AU - Swoboda, Paul
ID - 5557
KW - discrete tomography
TI - Synthetic discrete tomography problems
ER -
TY - JOUR
AB - 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).
AU - Kazda, Alexandr
ID - 1612
IS - 1
JF - Algebra Universalis
TI - CSP for binary conservative relational structures
VL - 75
ER -
TY - JOUR
AB - 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.
AU - Kolmogorov, Vladimir
AU - Takhanov, Rustem
ID - 1794
IS - 1
JF - Algorithmica
TI - Inference algorithms for pattern-based CRFs on sequence data
VL - 76
ER -
TY - CONF
AB - 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.
AU - Kolmogorov, Vladimir
ID - 1193
T2 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science
TI - Commutativity in the algorithmic Lovasz local lemma
VL - 2016-December
ER -