IDA - Department of Computer and Information Science

Programme

Michał Wrona will speak on Thursday, March 8, 13:15
Room: Donald Knuth
Title: Equivalence constraints

The following result for finite structures Gamma could hold for all countably infinite omega-categorical structures Gamma: either the model-complete core of Gamma interprets all finite structures primitively positively with parameters, or there is a homomorphism f from Gamma^k to Gamma, for some finite k, and an automorphism alpha of Gamma such that for all x_1,...,x_n, f(x_1,...,x_k) = alpha(f(x_2,...,x_k,x_1)). This conjecture has been confirmed for all infinite structures Gamma that have a first-order definition over (Q;<), and for all structures that are definable over the countably infinite universal homogeneous graph.

In this paper, we verify the conjecture for all structures that are definable over an equivalence relation with infinitely many infinite classes. Our result implies a complexity dichotomy (into NP-complete and P) for a family of constraint satisfaction problems which we call equivalence constraint satisfaction problems.

This is joint work with Manuel Bodirsky.

Previous Speakers

2011

Johan Thapper at LIX, École Polytechnique, France, will speak on Thursday, October 6, 15:15
Room: Donald Knuth
Title: Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets

A famous result by Jeavons, Cohen, and Gyssens [1] shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. The same statement is false for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from AI, can be formulated with constraint languages that are well-behaved from a model-theoretic point of view; the automorphism group of these constraint languages tends to be large in the sense that the number of orbits of n-subsets of the automorphism group is bounded by some function in n.

I will describe a generalisation of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n-subsets grows sub-exponentially in n which shows that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes many CSPs that cannot be solved by Datalog.

This is joint work with Manuel Bodirsky and Dugald Macpherson.

[1] Peter Jeavons, David A. Cohen, Marc Gyssens: Closure properties of constraints. J. ACM 44(4): 527-548 (1997)

Mikael Call at MAI, will speak on Wednesday, June 8, 15:15
Room: John von Neumann
Title: Complexity of Inverse Shortest Path Routing

Abstract:
The inverse shortest path routing problem is to decide if a set of tentative routing patterns is simultaneously realizable. A routing pattern is defined by its destination and two arc subsets of required shortest path arcs and prohibited non-shortest path arcs. A set of tentative routing patterns is simultaneously realizable if there is a cost vector such that for all routing patters it holds that all shortest path arcs are in some shortest path and no non-shortest path arc is in any shortest path to the destination of the routing pattern. Our main result is that this problem is NP-complete, contrary to what has been claimed earlier in the literature.
Inverse shortest path routing problems naturally arise as a subproblem in bilevel programs where the lower level consists of shortest path problems. Prominent applications that fit into this framework include traffic engineering in IP networks using OSPF or IS-IS and in Stackelberg network pricing games.
In this paper we focus on the common subproblem that arises if the bilevel program is linearized and solved by branch-and-cut. Then, it must repeatedly be decided if a set of tentative routing patterns is realizable. In particular, an NP-completeness proof for this problem is given.

Mikael Asplund at the Real-Time Systems Lab, will speak on Thursday, May 26, 13:15
Room: John von Neumann
Title: Worst-case Latency of Broadcast in Intermittently Connected Networks

Abstract:
TBA

Ola Svensson at KTH, Stockholm speaks on Thursday, January 27, 15:15
Room: John von Neumann
Title: Santa Claus Schedules Jobs on Unrelated Machines

Abstract:
One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where a job can only be assigned to a given subset of the machines on which it has the same processing time. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5 which is also the best known lower bound for the general version.
In this talk, we give an overview of the proof of a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 1.9412. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee, but is not known to converge in polynomial time.

2010

Magnus Wahlström at Max Planck Institut für Informatik, Saarbrücken, Germany speaks on Thursday, December 16, 15:15
Room: Donald Knuth
Title: Edge Bipartization - Old and New Results

Abstract:
Edge bipartization, also known an Min Uncut, is the problem of removing at most k edges from a graph so that the remaining graph is bipartite; it is NP-hard, as the solution is the complement of a max cut. I present the FPT algorithm by Guo et al. (FPT meaning an algorithm with running time f(k)*poly(n); in this case f(k)=2^k), and sketch some work-in-progress and more recent results.

Stefanie Kosuch speaks on Monday, November 29, 15:15
Room: John von Neumann
Title: The Two-Stage Knapsack Problem (and the question what to bring to Sweden in a random car)

Abstract:
Given a knapsack and a set of items each having a particular weight and value. The knapsack problem consists of choosing among these items a subset such that (i) the total weight of the chosen items does respect a given weight constraint (the capacity of the knapsack) and (ii) the total value of the chosen items is maximized. Applications of this famous and well studied problem can be found in logistics, resource allocation, scheduling, network optimization and several other fields. However, most real life problems are non-deterministic in the sense that some of the parameters are not (exactly) known at the moment when the decision has to be made.
In this presentation we study the case where the item weights are random and the decision is made in two stages: In the first stage, while the weights are still unknown, a pre-decision is made based on some statistical knowledge about the underlying weight distribution(s). In the second stage, i.e. after the item weights have come to be known, a corrective decision can be made. More precisely, items can be removed and/or added in order to make the capacity constraint be satisfied or to increase the total gain.
We study the resulting Two-Stage Knapsack Problem under two assumptions: the assumption of independently normally distributed weights and the assumption that the weight vector has only a finite number of possible outcomes (finite scenario model). In the former case, upper and lower bounds are proposed. The latter problem variant is studied under the aspect of approximability.

2009

Rustem Takhanov speaks on Wednesday, October 14, 15:15
Room: Donald Knuth
Title: Dichotomy theorem for general Minimum Cost Homomorphisms Problem

Abstract:
In the classical Constraint Satisfaction Problem(CSP) two finite models are given and we are asked to find their homomorphism. In the MinHom problem, besides the models, a set of weighted pairs of elements of this two models is given and the task is to find a homomorphism that maximizes the weight of pairs consistent with the homomorphism, i.e. pairs for which homomorphism maps the first element of the pair to the second element.

MinHom can be considered as a generic model for a class of combinatorial optimization problems, one of which is a maximal independent set. It appears naturally in defence logistic and supervised learning. This problem shares a lot of common with the classical CSP. We show that it allows similar algebraic approach to the classification of tractable cases of this problem that connects it with relational and functional clones of multi-valued logic. Using this approach we obtain complete classification of polynomially tractable subcases of MinHom. As a result of this classification we confirm general dichotomy conjecture that was given for various special cases of MinHom in terms of digraph theory.

The paper is available at the archive.

Manuel Bodirsky speaks on Tuesday, April 21, 15:15
Room: Alan Turing
Title: Introduction to Constraint Satisfaction Complexity and Applications in Spatial and Temporal Reasoning

This is a part of the SaS-seminar.

Abstract:
The constraint satisfaction framework is known to be sufficiently rich and expressive for representing problems occurring in a wide variety of industrial and scientific applications. This has led to the development of constraint programming languages and very successful commercial constraint solvers.

Due to the importance of the constraint satisfaction problem and the fact that it is in general a computationally hard problem, much research has been devoted to understanding its computational complexity and finding restricted cases that can be solved efficiently.

Qualitative temporal and spatial reasoning is a well-established area in artificial intelligence. The computational complexity of various reasoning tasks has been a central topic in this area, and there are many surprisingly rich formalisms where reasoning is polynomial-time tractable.

We apply techniques from constraint satisfaction complexity to give systematic complexity results for temporal and spatial reasoning formalisms. In particular, we use the so-called universal-algebraic approach that was originally developed for finite domain constraint satisfaction problems, and generalize it to study infinite domain constraint satisfaction problems.

Onsdagen 1/4 kl. 13 talar Fredrik Kuivinen om sina diamanter
Lokal: Kompakta rummet (MAI)
Titel: Submodular function minimization on diamonds

Detta seminarium hålls i Optimeringsläras regi

Abstract:
Given a positive integer n and a finite lattice (L; &cap, &cup) (that is, L is a poset with greatest lower bounds &cap and least upper bounds &cup), a function f : L^n -> R is said to be submodular if

f(a &cap b) + f(a &cup b) &le f(a) + f(b)

for all a, b &isin L^n. It is known that for certain lattices L if one is given oracle access to a submodular function mapping L^n into R one can find a minimizer of f (that is, a lattice element m &isin L^n such that min_{x &isin L^n} f(x) = f(m)) in time polynomial in n. However, such a result is not known to hold for all finite lattices.

In this talk I will present some results on this problem for the case when L is a diamond (the five element modular non-distributive lattice). I will also mention some connections to the Max CSP-problem.

Torsdagen 19/2 kl. 13 talar Kaj Holmberg
Lokal: John von Neumann
Titel: Graph Optimization Approaches for Minimal Rerouting in Symmetric Three Stage Clos Networks

Abstract:
Considering routing in symmetrical three stage Clos networks, we search for the routing of an additional connection that requires the least rearrangements, i.e. the minimal number of changes of already routed connections. We describe polynomial methods, based on matchings and edge colorings. The basic idea is to swap colors along alternating paths. The paths need to be maximal, and the shortest of these maximal paths is chosen, since it minimizes the rerouting that needs to be done. Computational tests confirm the efficiency of the approach.

2008

Tisdagen 16/12 kl. 10 talar Andrzej Szalas
Lokal: John von Neumann
Titel: On a Logical Approach to Estimating Computational Complexity of Potentially Intractable Problems

Abstract:
The talk will present a purely logical approach to estimating computational complexity of potentially intractable problems and illustrate the approach on the case of the transversal hypergraph problem, which has attracted a great deal of attention. The complexity of the problem remains unsolved for over twenty years. Given two hypergraphs, G and H, the problem depends on checking whether G is the transversal hypergraph of H.

A logical characterization of minimal transversals of a given hypergraph will be discussed. It will be shown that checking whether G is included in the transversal hypergraph of H is tractable. For the opposite inclusion the problem still remains open. However, an interpretation the resulting quantifier sequences in terms of determinism and bounded nondeterminism will be provided.

The discussed results give better upper bounds than those known from the literature, e.g., in the case when hypergraph H has a sub-logarithmic number of hyperedges and (for the deterministic case) all hyperedges have the cardinality bounded by a function sub-linear wrt maximum of sizes of G and H.

Fredagen 12/12 kl. 13-14 talar Jan Snellman (MAI)
Lokal: Donald Knuth
Titel: Kommutativa och icke-kommutativa termordningar

Abstract:
TBA

Tisdagen 30/9 kl. 15 talar Gustav Nordh
Lokal: Donald Knuth
Titel: Mellan kokloner och partiella kokloner

Abstract:
Följande resultat som visades av Peter Jeavons 1998 är en av hörnstenarna i den algebraiska metoden för att analysera komplexiteten hos villkorsproblem med avseende på begränsningar av typerna av tillåtna villkor.

• Givet en mängd relationer S och en ändlig delmängd S' av koklonen som genereras av S, då finns en polynomisk reduktion från CSP(S') till CSP(S).

Dock faller resultatet ovan för flera närbesläktade varianter av CSP(S) problemet, t.ex. ENUMCSP(S) (räkna upp lösningarna till ett CSP(S) problem). Dessutom är reduktionen ovan inte storleksbevarande.

Om man istället byter ut koklon mot partiell koklon i resultatet ovan så får man en polynomisk reduktion som är storleksbevarande och fungerar för alla upptänkliga varianter av CSP(S) problemet. Problemet är nu istället att strukturen för partiella kokloner är mycket mer komplicerad än för kokloner (det finns ett överuppräkneligt antal partiella kokloner över Boolesk domän och strukturen är till stor del okänd, att jämföra med "vanliga" kokloner över Boolesk domän där antalet är uppräkneligt och strukturen visades av Emil Post 1921).

Det vore således önskvärt att undersöka konstruktioner som ligger mellan kokloner och partiella kokloner. Vi undersöker två sådana konstruktioner: "frysta kokloner" och "trogna kokloner". Vi undersöker deras egenskaper och, över Boolesk domän, deras struktur. Med hjälp av frysta kokloner hittar vi också det lättaste NP-fullständiga SAT(S) problemet (under antagandet P != NP).

Tisdagen 17/6 kl. 13 talar Wlodek Drabent
Lokal: Donald Knuth
Titel: It is declarative; or proving correctness of logic programs

Abstract:
Logic programming is a declarative programming paradigm. Programs are usually much closer to their (informal or formal) specifications than in imperative programming. But a claim that logic programs are their own specifications is too superficial.

Some important textbooks present a strange approach to dealing with logic programs correctness. It is based on their operational semantics. This makes the approach unnecessarily complicated. Moreover, if discussing correctness required thinking in terms of operational semantics then logic programming should not be called declarative. We contradict this opinion, by presenting a declarative way of proving programs correct.

This work is a few years old, but it is related to basics of logic programming and is not widely known. So it may be of interest.

Presentationen är baserad på: W. Drabent, M. Milkowska (2005). Proving Correctness and Completeness of Normal Programs - a Declarative Approach. Theory and Practice of Logic Programming, 5(6):669-711, 2005, available from CoRR.

Tisdagen 27/5 kl. 13 talar Jan-Åke Larsson från MAI
Lokal: John von Neumann
Titel:

Abstract:
Länk till artikeln som presentation baseras på.

Tisdagen 20/5 kl. 13 talar Thomas Kaijser från MAI
Lokal: Donald Knuth
Titel: En modifiering av primal-dual algoritmen för stora transportproblem då kostnadsfunktionen bestäms av en avståndsfunktion.

Abstract:
Den ungerska algoritmen för lösande av assignment-problemet är av komplexitet O(N³). Transportproblemet (balanserade) från N källor till N sänkor är av komplexitet O(MN²) där M anger totalmassan. Metoden tar ej hänsyn till eventuella reuljäriteter hos kostnadsfunktionen. Under senare år har lösningen på transportproblemet använts som avståndsmått mellan bilder. (The earth mover's distance.) På 90-talet ägnade jag mycket tid åt att finna en algoritm för stora transportproblem ( N ~ 60000). Jag ville ha en algoritm som löser stora problem på ändlig tid.

Min metod är en modifiering av av primal-dual algoritmen i vilken jag lyckas reducera antal operationer för att bestämma minimum av avstånden mellan de omärkta "källorna" i den ena bilden och de märkta "sänkorna" i den andra bilden, vilket normalt är ett steg av komplexitet O(N²), men som nu är av komplexitet O(N) där O't är av storleksordning 10 till 100.

Onsdagen 5/3 kl. 13 i Donald Knuth talar Peter Jonsson
Titel: CSP-problem över oändliga domäner

Abstract:
CSP-problem över oändliga domäner har periodvis studerats intensivt inom AI. Under de senaste åren har sådana problem dessutom fått uppmärksamhet från flera andra håll såsom komplexitetsteori och algebra. I denna kortfattade översikt kommer jag att:

1) Peka ut några viktiga skillnader mellan ändliga och oändliga CSPer;

2) Ge en bakgrund till varför man så ofta nöjer sig med att studera relationer definierade via första-ordningens logik; och

3) Presentera några bevismetoder.

Onsdagen 27/2 kl. 13 i Donald Knuth talar Fredrik Kuivinen

Abstract:
Jag kommer att prata om submodulära funktioner på mängder och diamanter. Jag kommer ta upp kopplingen mellan submodulärfunktionsminimering och Max CSP-problemet. Ett relativt färskt resultat som ger en karaktärisering av minimina till submodulära funktioner på diamanter kommer att presenteras.

Onsdagen 20/2 kl. 13 i Augusta Ada Lovelace talar Johan Thapper
Titel: Max-cut och Kneser-grafer

Abstract:
Vi presenterar ett resultat om mängdsystem och en följdförmodan på hur Max cut i Kneser-grafer ser ut. Detta är hämtat ur artikeln Set systems with few disjoint pairs av Béla Bollobás och Imre Leader Vi kommer att börja med att definiera Kneser-grafer och ge några grundläggande egenskaper hos dem. Tillämpningen av det hela har att göra med approximerbarheten hos Max H-Colouring då H är en Kneser-graf och står att finna i rapporten Approximability Distance in the Space of H-Colourable Problems av Tommy Färnqvist, Peter Jonsson och Johan Thapper.

Torsdagen 14/2 kl. 13 i John von Neumann talar Tommy Färnqvist
Titel: Minimum Homomorphisms, Maximum Solutions and Unbounded Tree-width

Abstract:
We will look at two structurally restricted homomorphism problems (MIN HOM and MAX SOL). Specifically we will try to highlight details in the proofs of intractability when the left hand side input structures of these problems have unbounded tree-width that appear in the paper Bounded Tree-width and CSP-related Problems by Tommy Färnqvist and Peter Jonsson.