6 Search Results for "Brown, David"

Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.5
Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets

Authors: Laurent David, Colin Defant, Michael Joseph, Matthew Macauley, and Alex McDonough

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
Though iterated maps and dynamical systems are not new to combinatorics, they have enjoyed a renewed prominence over the past decade through the elevation of the subfield that has become known as dynamical algebraic combinatorics. Some of the problems that have gained popularity can also be cast and analyzed as finite asynchronous cellular automata (CA). However, these two fields are fairly separate, and while there are some individuals who work in both, that is the exception rather than the norm. In this article, we will describe our ongoing work on toggling independent sets on graphs. This will be preceded by an overview of how this project arose from new combinatorial problems involving homomesy, toggling, and resonance. Though the techniques that we explore are directly applicable to ECA rule 1, many of them can be generalized to other cellular automata. Moreover, some of the ideas that we borrow from cellular automata can be adapted to problems in dynamical algebraic combinatorics. It is our hope that this article will inspire new problems in both fields and connections between them.
Cite as

Laurent David, Colin Defant, Michael Joseph, Matthew Macauley, and Alex McDonough. Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{david_et_al:OASIcs.AUTOMATA.2021.5,
  author =	{David, Laurent and Defant, Colin and Joseph, Michael and Macauley, Matthew and McDonough, Alex},
  title =	{{Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{5:1--5:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.5},
  URN =		{urn:nbn:de:0030-drops-140145},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.5},
  annote =	{Keywords: Asynchronous cellular automata, Covering space, Coxeter element, Dynamical algebraic combinatorics, Group action, Homomesy, Independent set, Resonance, Toggling, Toric equivalence}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.8
Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension

Authors: Amariah Becker, Philip N. Klein, and David Saulpic

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
The concept of bounded highway dimension was developed to capture observed properties of road networks. We show that a graph of bounded highway dimension with a distinguished root vertex can be embedded into a graph of bounded treewidth in such a way that u-to-v distance is preserved up to an additive error of epsilon times the u-to-root plus v-to-root distances. We show that this embedding yields a PTAS for Bounded-Capacity Vehicle Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours, where each client is visited by some tour and each tour covers at most Q units of client demand. Our PTAS can be extended to handle penalties for unvisited clients. We extend this embedding result to handle a set S of root vertices. This result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle Routing: the tours can go from one depot to another. The embedding result also implies that, for fixed k, there is a PTAS for k-Center in graphs of bounded highway dimension. In this problem, the goal is to minimize d so that there exist k vertices (the centers) such that every vertex is within distance d of some center. Similarly, for fixed k, there is a PTAS for k-Median in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the k centers.
Cite as

Amariah Becker, Philip N. Klein, and David Saulpic. Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ESA.2018.8,
  author =	{Becker, Amariah and Klein, Philip N. and Saulpic, David},
  title =	{{Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.8},
  URN =		{urn:nbn:de:0030-drops-94710},
  doi =		{10.4230/LIPIcs.ESA.2018.8},
  annote =	{Keywords: Highway Dimension, Capacitated Vehicle Routing, Graph Embeddings}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.3
A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees

Authors: Amariah Becker

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
Given a set of clients with demands, the Capacitated Vehicle Routing problem is to find a set of tours that collectively cover all client demand, such that the capacity of each vehicle is not exceeded and such that the sum of the tour lengths is minimized. In this paper, we provide a 4/3-approximation algorithm for Capacitated Vehicle Routing on trees, improving over the previous best-known approximation ratio of (sqrt{41}-1)/4 by Asano et al.[Asano et al., 2001], while using the same lower bound. Asano et al. show that there exist instances whose optimal cost is 4/3 times this lower bound. Notably, our 4/3 approximation ratio is therefore tight for this lower bound, achieving the best-possible performance.
Cite as

Amariah Becker. A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{becker:LIPIcs.APPROX-RANDOM.2018.3,
  author =	{Becker, Amariah},
  title =	{{A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.3},
  URN =		{urn:nbn:de:0030-drops-94075},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.3},
  annote =	{Keywords: Approximation algorithms, Graph algorithms, Capacitated vehicle routing}
}
Document
DOI: 10.4230/LITES-v002-i002-a001
From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation

Authors: Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens

Published in: LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2

Abstract
Our objective is to facilitate the development of complex time-triggered systems by automating the allocation and scheduling steps. We show that full automation is possible while taking into account the elements of complexity needed by a complex embedded control system. More precisely, we consider deterministic functional specifications provided (as often in an industrial setting) by means of synchronous data-flow models with multiple modes and multiple relative periods. We first extend this functional model with an original real-time characterization that takes advantage of our time-triggered framework to provide a simpler representation of complex end-to-end flow requirements. We also extend our specifications with additional non-functional properties specifying partitioning, allocation, and preemptability constraints. Then, we provide novel algorithms for the off-line scheduling of these extended specifications onto partitioned time-triggered architectures à la ARINC 653. The main originality of our work is that it takes into account at the same time multiple complexity elements: various types of non-functional properties (real-time, partitioning, allocation, preemptability) and functional specifications with conditional execution and multiple modes. Allocation of time slots/windows to partitions can be fully or partially provided, or synthesized by our tool. Our algorithms allow the automatic allocation and scheduling onto multi-processor (distributed) systems with a global time base, taking into account communication costs. We demonstrate our technique on a model of space flight software system with strong real-time determinism requirements.
Cite as

Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens. From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation. In LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2, pp. 01:1-01:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{carle_et_al:LITES-v002-i002-a001,
  author =	{Carle, Thomas and Potop-Butucaru, Dumitru and Sorel, Yves and Lesens, David},
  title =	{{From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:30},
  ISSN =	{2199-2002},
  year =	{2015},
  volume =	{2},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LITES-v002-i002-a001},
  doi =		{10.4230/LITES-v002-i002-a001},
  annote =	{Keywords: Time-triggered, Off-line real-time scheduling, Temporal partitioning}
}
Document
DOI: 10.4230/DagSemProc.09291.9
Computational Artistic Creativity and its Evaluation

Authors: David Brown

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)

Abstract
For artistic creativity, in comparison to design creativity, requirements may not exist, and constraints on the artifact (the artistic “product”) are usually looser or absent. Many computational creativity systems produce artistic artifacts, but such results can be judged in a variety of ways: by a variety of artistic standards or by the perceiver’s "taste", for example. There is less chance of a generated artifact being judged in a single, clear and concrete fashion, so the standards may be softer and perhaps easier to satisfy: certainly harder to make computational. With regard to taste, Boden (1994) quotes, "I don’t know anything about art, but I know what I like”. If this were true in general, then there would be as many tests of the creativity of an artifact as there are people!
Cite as

David Brown. Computational Artistic Creativity and its Evaluation. In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brown:DagSemProc.09291.9,
  author =	{Brown, David},
  title =	{{Computational Artistic Creativity and its Evaluation}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.9},
  URN =		{urn:nbn:de:0030-drops-22209},
  doi =		{10.4230/DagSemProc.09291.9},
  annote =	{Keywords: Evaluation, design creativity, artistic creativity, novelty, resolution, style, function}
}
Document
DOI: 10.4230/DagSemProc.09291.22
Notes from the Discussion Group on "Evaluation"

Authors: David Brown

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)

Abstract
Group Members: Harold Cohen, Maggie Boden, Dave Brown, Paul Brown, Oliver Deussen, Philip Galanter. These notes represent approximately what was discussed by the group members over a period of several hours over two days. There has been some attempt to organize the material, but little attempt to expand it to make it coherent—we rambled, so do the notes. The notes, and this report, were recorded, organized, and elaborated into this form by Dave Brown.
Cite as

David Brown. Notes from the Discussion Group on "Evaluation". In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brown:DagSemProc.09291.22,
  author =	{Brown, David},
  title =	{{Notes from the Discussion Group on "Evaluation"}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.22},
  URN =		{urn:nbn:de:0030-drops-22128},
  doi =		{10.4230/DagSemProc.09291.22},
  annote =	{Keywords: Evaluation, art, artistic, creativity}
}
  • Refine by Author
  • 2 Becker, Amariah
  • 2 Brown, David
  • 1 Carle, Thomas
  • 1 David, Laurent
  • 1 Defant, Colin
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Routing and network design problems
  • 1 Computer systems organization
  • 1 Computer systems organization → Real-time systems
  • 1 Hardware → Cellular neural networks
  • 1 Mathematics of computing → Combinatoric problems
  • Show More...

  • Refine by Keyword
  • 2 Evaluation
  • 1 Approximation algorithms
  • 1 Asynchronous cellular automata
  • 1 Capacitated Vehicle Routing
  • 1 Capacitated vehicle routing
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2009
  • 2 2018
  • 1 2015
  • 1 2021

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact