11 Search Results for "Cote, Marie-Claude"


Document
MDD Archive for Boosting the Pareto Constraint

Authors: Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)


Abstract
Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in CP the global constraint Pareto was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of Pareto optimal solutions, called the archive. This constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. The complexity of these operations depends on the size of the archive. In this paper, we propose to use a multi-valued Decision Diagram (MDD) to represent the archive of Pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-knapsack problems the validity of our approach.

Cite as

Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin. MDD Archive for Boosting the Pareto Constraint. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{malalel_et_al:LIPIcs.CP.2023.24,
  author =	{Malalel, Steve and Malapert, Arnaud and Pelleau, Marie and R\'{e}gin, Jean-Charles},
  title =	{{MDD Archive for Boosting the Pareto Constraint}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.24},
  URN =		{urn:nbn:de:0030-drops-190610},
  doi =		{10.4230/LIPIcs.CP.2023.24},
  annote =	{Keywords: Constraint Programming, Global Constraint, MDD, Multi-Objective Problem, Pareto Constraint}
}
Document
On the Width of Complicated JSJ Decompositions

Authors: Kristóf Huszár and Jonathan Spreer

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)


Abstract
Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "sufficiently complicated" JSJ decomposition of a 3-manifold enforces a "complicated structure" for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold M yields a linear lower bound on its treewidth tw (M) (resp. pathwidth pw(M)), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of M. We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth - previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds.

Cite as

Kristóf Huszár and Jonathan Spreer. On the Width of Complicated JSJ Decompositions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{huszar_et_al:LIPIcs.SoCG.2023.42,
  author =	{Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan},
  title =	{{On the Width of Complicated JSJ Decompositions}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.42},
  URN =		{urn:nbn:de:0030-drops-178920},
  doi =		{10.4230/LIPIcs.SoCG.2023.42},
  annote =	{Keywords: computational 3-manifold topology, fixed-parameter tractability, generalized Heegaard splittings, JSJ decompositions, pathwidth, treewidth, triangulations}
}
Document
Grabbing Olives on Linear Pizzas and Pissaladières

Authors: Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
In this paper we revisit the problem entitled Sharing a Pizza stated by P. Winkler by considering a new puzzle called Sharing a Pissaladiere. The game is played by two polite coatis Alice and Bob who share a pissaladière (a p×q grid) which is divided into rectangular slices. Alice starts in a corner and then the coatis alternate removing a remaining slice adjacent to at most two other slices. On some slices there are precious olives of Nice and the aim of each coati is to grab the maximum number of olives. We first study the particular case of 1×n grid (i.e. a path) where the game is a graph grabbing game known as Sharing a linear pizza. In that case each player can take only an end vertex of the remaining path. These problems are particular cases of a new class of games called d-degenerate games played on a graph with non negative weights assigned to the vertices with the rule that coatis alternatively take a vertex of degree at most d. Our main results are the following. We give optimal strategies for paths (linear pizzas) with no two adjacent weighty vertices. We also give a recurrence formula to compute the gains which depend only on the parity of n and of the respective parities of weighty vertices with a complexity in O(h²) where h denotes the number of parity changes in the weighty vertices. When the weights are only {0,1} we reduce the computation of the average number of olives collected by each player to a word counting problem. We solve Sharing a pissaladière with {0,1} weights, when there is one olive or 2 olives. In that case Alice (resp. Bob) grabs almost all the olives if the number of vertices of the grid n = p×q is odd (resp. even). We prove that for a 2×q grid with a fixed number k of olives Bob grabs at least ⌈(k-1)/3⌉ olives and almost always grabs all the k olives.

Cite as

Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard. Grabbing Olives on Linear Pizzas and Pissaladières. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2022.12,
  author =	{Bermond, Jean-Claude and Havet, Fr\'{e}d\'{e}ric and Cosnard, Michel},
  title =	{{Grabbing Olives on Linear Pizzas and Pissaladi\`{e}res}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.12},
  URN =		{urn:nbn:de:0030-drops-159826},
  doi =		{10.4230/LIPIcs.FUN.2022.12},
  annote =	{Keywords: Grabbing game, degenerate graph, path, grid}
}
Document
Tracing Isomanifolds in ℝ^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations

Authors: Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.

Cite as

Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken. Tracing Isomanifolds in ℝ^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2021.17,
  author =	{Boissonnat, Jean-Daniel and Kachanovich, Siargey and Wintraecken, Mathijs},
  title =	{{Tracing Isomanifolds in \mathbb{R}^d in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.17},
  URN =		{urn:nbn:de:0030-drops-138163},
  doi =		{10.4230/LIPIcs.SoCG.2021.17},
  annote =	{Keywords: Coxeter triangulation, Kuhn triangulation, permutahedron, PL-approximations, isomanifolds/solution manifolds/isosurfacing}
}
Document
System Description
A Type Checker for a Logical Framework with Union and Intersection Types (System Description)

Authors: Claude Stolze and Luigi Liquori

Published in: LIPIcs, Volume 167, 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)


Abstract
We present the syntax, semantics, typing, subtyping, unification, refinement, and REPL of BULL, a prototype theorem prover based on the Δ-Framework, i.e. a fully-typed Logical Framework à la Edinburgh LF decorated with union and intersection types, as described in previous papers by the authors. BULL also implements a subtyping algorithm for the Type Theory Ξ of Barbanera-Dezani-de'Liguoro. BULL has a command-line interface where the user can declare axioms, terms, and perform computations and some basic terminal-style features like error pretty-printing, subexpressions highlighting, and file loading. Moreover, it can typecheck a proof or normalize it. These terms can be incomplete, therefore the typechecking algorithm uses unification to try to construct the missing subterms. BULL uses the syntax of Berardi’s Pure Type Systems to improve the compactness and the modularity of the kernel. Abstract and concrete syntax are mostly aligned and similar to the concrete syntax of Coq. BULL uses a higher-order unification algorithm for terms, while typechecking and partial type inference are done by a bidirectional refinement algorithm, similar to the one found in Matita and Beluga. The refinement can be split into two parts: the essence refinement and the typing refinement. Binders are implemented using commonly-used de Bruijn indices. We have defined a concrete language syntax that will allow user to write Δ-terms. We have defined the reduction rules and an evaluator. We have implemented from scratch a refiner which does partial typechecking and type reconstruction. We have experimented BULL with classical examples of the intersection and union literature, such as the ones formalized by Pfenning with his Refinement Types in LF and by Pierce. We hope that this research vein could be useful to experiment, in a proof theoretical setting, forms of polymorphism alternatives to Girard’s parametric one.

Cite as

Claude Stolze and Luigi Liquori. A Type Checker for a Logical Framework with Union and Intersection Types (System Description). In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 167, pp. 37:1-37:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{stolze_et_al:LIPIcs.FSCD.2020.37,
  author =	{Stolze, Claude and Liquori, Luigi},
  title =	{{A Type Checker for a Logical Framework with Union and Intersection Types}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{37:1--37:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-155-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{167},
  editor =	{Ariola, Zena M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.37},
  URN =		{urn:nbn:de:0030-drops-123597},
  doi =		{10.4230/LIPIcs.FSCD.2020.37},
  annote =	{Keywords: Intersection types, Union types, Dependent types, Subtyping, Type checker, Refiner, \Delta-Framework}
}
Document
Extending Drawings of Graphs to Arrangements of Pseudolines

Authors: Alan Arroyo, Julien Bensmail, and R. Bruce Richter

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.

Cite as

Alan Arroyo, Julien Bensmail, and R. Bruce Richter. Extending Drawings of Graphs to Arrangements of Pseudolines. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{arroyo_et_al:LIPIcs.SoCG.2020.9,
  author =	{Arroyo, Alan and Bensmail, Julien and Richter, R. Bruce},
  title =	{{Extending Drawings of Graphs to Arrangements of Pseudolines}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.9},
  URN =		{urn:nbn:de:0030-drops-121672},
  doi =		{10.4230/LIPIcs.SoCG.2020.9},
  annote =	{Keywords: graphs, graph drawings, geometric graph drawings, arrangements of pseudolines, crossing numbers, stretchability}
}
Document
The Topological Correctness of PL-Approximations of Isomanifolds

Authors: Jean-Daniel Boissonnat and Mathijs Wintraecken

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.

Cite as

Jean-Daniel Boissonnat and Mathijs Wintraecken. The Topological Correctness of PL-Approximations of Isomanifolds. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2020.20,
  author =	{Boissonnat, Jean-Daniel and Wintraecken, Mathijs},
  title =	{{The Topological Correctness of PL-Approximations of Isomanifolds}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.20},
  URN =		{urn:nbn:de:0030-drops-121787},
  doi =		{10.4230/LIPIcs.SoCG.2020.20},
  annote =	{Keywords: PL-approximations, isomanifolds, solution manifolds, topological correctness}
}
Document
The Delta-calculus: Syntax and Types

Authors: Luigi Liquori and Claude Stolze

Published in: LIPIcs, Volume 131, 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)


Abstract
We present the Delta-calculus, an explicitly typed lambda-calculus with strong pairs, projections and explicit type coercions. The calculus can be parametrized with different intersection type theories T, e.g. the Coppo-Dezani, the Coppo-Dezani-Sallé, the Coppo-Dezani-Venneri and the Barendregt-Coppo-Dezani ones, producing a family of Delta-calculi with related intersection typed systems. We prove the main properties like Church-Rosser, unicity of type, subject reduction, strong normalization, decidability of type checking and type reconstruction. We state the relationship between the intersection type assignment systems à la Curry and the corresponding intersection typed systems à la Church by means of an essence function translating an explicitly typed Delta-term into a pure lambda-term one. We finally translate a Delta-term with type coercions into an equivalent one without them; the translation is proved to be coherent because its essence is the identity. The generic Delta-calculus can be parametrized to take into account other intersection type theories as the ones in the Barendregt et al. book.

Cite as

Luigi Liquori and Claude Stolze. The Delta-calculus: Syntax and Types. In 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 131, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{liquori_et_al:LIPIcs.FSCD.2019.28,
  author =	{Liquori, Luigi and Stolze, Claude},
  title =	{{The Delta-calculus: Syntax and Types}},
  booktitle =	{4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-107-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{131},
  editor =	{Geuvers, Herman},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2019.28},
  URN =		{urn:nbn:de:0030-drops-105354},
  doi =		{10.4230/LIPIcs.FSCD.2019.28},
  annote =	{Keywords: intersection types, lambda calculus \`{a} la Church and \`{a} la Curry, proof-functional logics}
}
Document
The Delta-Framework

Authors: Furio Honsell, Luigi Liquori, Claude Stolze, and Ivan Scagnetto

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)


Abstract
We introduce the Delta-framework, LF_Delta, a dependent type theory based on the Edinburgh Logical Framework LF, extended with the strong proof-functional connectives, i.e. strong intersection, minimal relevant implication and strong union. Strong proof-functional connectives take into account the shape of logical proofs, thus reflecting polymorphic features of proofs in formulae. This is in contrast to classical or intuitionistic connectives where the meaning of a compound formula depends only on the truth value or the provability of its subformulae. Our framework encompasses a wide range of type disciplines. Moreover, since relevant implication permits to express subtyping, LF_Delta subsumes also Pfenning's refinement types. We discuss the design decisions which have led us to the formulation of LF_Delta, study its metatheory, and provide various examples of applications. Our strong proof-functional type theory can be plugged in existing common proof assistants.

Cite as

Furio Honsell, Luigi Liquori, Claude Stolze, and Ivan Scagnetto. The Delta-Framework. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 37:1-37:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{honsell_et_al:LIPIcs.FSTTCS.2018.37,
  author =	{Honsell, Furio and Liquori, Luigi and Stolze, Claude and Scagnetto, Ivan},
  title =	{{The Delta-Framework}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{37:1--37:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.37},
  URN =		{urn:nbn:de:0030-drops-99367},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.37},
  annote =	{Keywords: Logic of programs, type theory, lambda-calculus}
}
Document
How long does it take for all users in a social network to choose their communities?

Authors: Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, and Dorian Mazauric

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)


Abstract
We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (i.e., independent sets in the conflict graph G^- =(V,E) that represents the enmities between users). The dynamics goes on as long as there exists any set of at most k users, k being any fixed parameter, that can change their current groups in the partition simultaneously, in such a way that they all strictly increase their utilities (number of friends i.e., the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were O(|V|alpha(G^-)) for k <= 2 and O(|V|^3) for k=3, with alpha(G^-) being the independence number of G^-. Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for k <= 2 the tight upper-bound O(|V| min {alpha(G^-), sqrt{|V|}}) and, when G^- is the empty graph, the exact value of order ((2|V|)^{3/2})/3. The time of convergence, for any fixed k >= 4, was conjectured to be polynomial [Escoffier et al., 2012][Kleinberg and Ligett, 2013]. In this paper we disprove this. Specifically, we prove that for any k >= 4, the maximum time of convergence is an Omega(|V|^{Theta(log{|V|})}).

Cite as

Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, and Dorian Mazauric. How long does it take for all users in a social network to choose their communities?. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2018.6,
  author =	{Bermond, Jean-Claude and Chaintreau, Augustin and Ducoffe, Guillaume and Mazauric, Dorian},
  title =	{{How long does it take for all users in a social network to choose their communities?}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.6},
  URN =		{urn:nbn:de:0030-drops-87972},
  doi =		{10.4230/LIPIcs.FUN.2018.6},
  annote =	{Keywords: communities, social networks, integer partitions, coloring games, graphs}
}
Document
Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling

Authors: Marie-Claude Cote, Bernard Gendron, and Louis-Martin Rousseau

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)


Abstract
We present a new implicit formulation for shift scheduling problems, using context-free grammars to model regulation in the composition of shifts. From the grammar, we generate an integer programming (IP) model allowing the same set of shifts as Dantzig’s set covering model. When solved by a state-of-the- art IP solver on problems allowing a small number of shifts, our model, the set covering formulation and a typical implicit model from the literature yield comparable solving times. Moreover, on instances where many shifts are allowed, our model is superior and can encode a wider variety of constraints. Among others, multi-activity cases, which cannot be modeled by existing implicit formulations, can easily be captured with grammars.

Cite as

Marie-Claude Cote, Bernard Gendron, and Louis-Martin Rousseau. Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{cote_et_al:DagSemProc.09261.9,
  author =	{Cote, Marie-Claude and Gendron, Bernard and Rousseau, Louis-Martin},
  title =	{{Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.9},
  URN =		{urn:nbn:de:0030-drops-21775},
  doi =		{10.4230/DagSemProc.09261.9},
  annote =	{Keywords: Shift Scheduling, Implicit models, Integer Programming, Context-free grammars}
}
  • Refine by Author
  • 3 Liquori, Luigi
  • 3 Stolze, Claude
  • 2 Bermond, Jean-Claude
  • 2 Boissonnat, Jean-Daniel
  • 2 Wintraecken, Mathijs
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Lambda calculus
  • 1 Applied computing → Multi-criterion optimization and decision-making
  • 1 Mathematics of computing → Decision diagrams
  • Show More...

  • Refine by Keyword
  • 2 PL-approximations
  • 2 graphs
  • 1 Constraint Programming
  • 1 Context-free grammars
  • 1 Coxeter triangulation
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 3 2020
  • 2 2018
  • 2 2023
  • 1 2009
  • 1 2019
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail