14 Search Results for "Jones, Michael A."

Document
DOI: 10.4230/LIPIcs.SEA.2023.15
FREIGHT: Fast Streaming Hypergraph Partitioning

Authors: Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.
Cite as

Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz. FREIGHT: Fast Streaming Hypergraph Partitioning. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 15:1-15:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eyubov_et_al:LIPIcs.SEA.2023.15,
  author =	{Eyubov, Kamal and Fonseca Faraj, Marcelo and Schulz, Christian},
  title =	{{FREIGHT: Fast Streaming Hypergraph Partitioning}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.15},
  URN =		{urn:nbn:de:0030-drops-183657},
  doi =		{10.4230/LIPIcs.SEA.2023.15},
  annote =	{Keywords: Hypergraph partitioning, graph partitioning, edge partitioning, streaming}
}
Document
DOI: 10.4230/LITES.8.2.5
Bayesian Hybrid Automata: A Formal Model of Justified Belief in Interacting Hybrid Systems Subject to Imprecise Observation

Authors: Paul Kröger and Martin Fränzle

Published in: LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2

Abstract
Hybrid discrete-continuous system dynamics arises when discrete actions, e.g. by a decision algorithm, meet continuous behaviour, e.g. due to physical processes and continuous control. A natural domain of such systems are emerging smart technologies which add elements of intelligence, co-operation, and adaptivity to physical entities, enabling them to interact with each other and with humans as systems of (human-)cyber-physical systems or (H)CPSes.Various flavours of hybrid automata have been suggested as a means to formally analyse CPS dynamics. In a previous article, we demonstrated that all these variants of hybrid automata provide inaccurate, in the sense of either overly pessimistic or overly optimistic, verdicts for engineered systems operating under imprecise observation of their environment due to, e.g., measurement error. We suggested a revised formal model, called Bayesian hybrid automata, that is able to represent state tracking and estimation in hybrid systems and thereby enhances precision of verdicts obtained from the model in comparison to traditional model variants.In this article, we present an extended definition of Bayesian hybrid automata which incorporates a new class of guard and invariant functions that allow to evaluate traditional guards and invariants over probability distributions. The resulting framework allows to model observers with knowledge about the control strategy of an observed agent but with imprecise estimates of the data on which the control decisions are based.
Cite as

Paul Kröger and Martin Fränzle. Bayesian Hybrid Automata: A Formal Model of Justified Belief in Interacting Hybrid Systems Subject to Imprecise Observation. In LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2, pp. 05:1-05:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{kroger_et_al:LITES.8.2.5,
  author =	{Kr\"{o}ger, Paul and Fr\"{a}nzle, Martin},
  title =	{{Bayesian Hybrid Automata: A Formal Model of Justified Belief in Interacting Hybrid Systems Subject to Imprecise Observation}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{05:1--05:27},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.2.5},
  doi =		{10.4230/LITES.8.2.5},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/LITES-v005-i001-a004
A Static Analysis for the Minimization of Voters in Fault-Tolerant Circuits

Authors: Dmitry Burlyaev, Pascal Fradet, and Alain Girault

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract
We present a formal approach to minimize the number of voters in triple-modular redundant (TMR) sequential circuits. Our technique actually works on a single copy of the TMR circuit and considers a large class of fault mo dels of the form “at most 1 Single-Event Upset (SEU) or Single-Event Transient (SET) every k clock cycles”. Verification-based voter minimization guarantees that the resulting TMR circuit (i) is fault tolerant to the soft-errors defined by the fault model and (ii) is functionally equivalent to the initial TMR circuit. Our approach operates at the logic level and takes into account the input and output interface specifications of the circuit. Its implementation makes use of graph traversal algorithms, fixed-point iterations, and binary decision diagrams (BDD). Experimental results on the ITC’99 benchmark suite indicate that our method significantly decreases the number of inserted voters, yielding a hardware reduction of up to 55% and a clock frequency increase of up to 35% compared to full TMR. As our experiments show, if the SEU fault-model is replaced with the stricter fault-model of SET, it has a minor impact on the number of removed voters. On the other hand, BDD-based modelling of SET effects represents a more complex task than the modelling of an SEU as a bit-flip. We propose solutions for this task and explain the nature of encountered problems. We address scalability issues arising from formal verification with approximations and assess their efficiency and precision.
Cite as

Dmitry Burlyaev, Pascal Fradet, and Alain Girault. A Static Analysis for the Minimization of Voters in Fault-Tolerant Circuits. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 04:1-04:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{burlyaev_et_al:LITES-v005-i001-a004,
  author =	{Burlyaev, Dmitry and Fradet, Pascal and Girault, Alain},
  title =	{{A Static Analysis for the Minimization of Voters in Fault-Tolerant Circuits}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{04:1--04:26},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a004},
  doi =		{10.4230/LITES-v005-i001-a004},
  annote =	{Keywords: Digital Circuits, Fault-tolerance, Optimization, Static Analysis, Triple Modular Redundancy}
}
Document
DOI: 10.4230/LITES-v004-i001-a005
Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains

Authors: Eric W. D. Rozier, Kristin Y. Rozier, and Ulya Bayram

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1

Abstract
As data centers attempt to cope with the exponential growth of data, new techniques for intelligent, software-defined data centers (SDDC) are being developed to confront the scale and pace of changing resources and requirements.  For cost-constrained environments, like those increasingly present in scientific research labs, SDDCs also may provide better reliability and performability with no additional hardware through the use of dynamic syndrome allocation. To do so, the middleware layers of SDDCs must be able to calculate and account for complex dependence relationships to determine an optimal data layout.  This challenge is exacerbated by the growth of constraints on the dependence problem when available resources are both large (due to a higher number of syndromes that can be stored) and small (due to the lack of available space for syndrome allocation). We present a quantitative method for characterizing these challenges using an analysis of attack domains for high-dimension variants of the $n$-queens problem that enables performable solutions via the SMT solver Z3. We demonstrate correctness of our technique, and provide experimental evidence of its efficacy; our implementation is publicly available.
Cite as

Eric W. D. Rozier, Kristin Y. Rozier, and Ulya Bayram. Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 05:1-05:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{rozier_et_al:LITES-v004-i001-a005,
  author =	{Rozier, Eric W. D. and Rozier, Kristin Y. and Bayram, Ulya},
  title =	{{Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{05:1--05:26},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a005},
  doi =		{10.4230/LITES-v004-i001-a005},
  annote =	{Keywords: SMT, Data dependence, n-queens}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2016.2
QL: Object-oriented Queries on Relational Data

Authors: Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Schäfer

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
This paper describes QL, a language for querying complex, potentially recursive data structures. QL compiles to Datalog and runs on a standard relational database, yet it provides familiar-looking object-oriented features such as classes and methods, reinterpreted in logical terms: classes are logical properties describing sets of values, subclassing is implication, and virtual calls are dispatched dynamically by considering the most specific classes containing the receiver. Furthermore, types in QL are prescriptive and actively influence program evaluation rather than just describing it. In combination, these features enable the development of concise queries based on reusable libraries, which are written in a purely declarative style, yet can be efficiently executed even on very large data sets. In particular, we have used QL to implement static analyses for various programming languages, which scale to millions of lines of code.
Cite as

Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Schäfer. QL: Object-oriented Queries on Relational Data. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 2:1-2:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{avgustinov_et_al:LIPIcs.ECOOP.2016.2,
  author =	{Avgustinov, Pavel and de Moor, Oege and Jones, Michael Peyton and Sch\"{a}fer, Max},
  title =	{{QL: Object-oriented Queries on Relational Data}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{2:1--2:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.2},
  URN =		{urn:nbn:de:0030-drops-60968},
  doi =		{10.4230/LIPIcs.ECOOP.2016.2},
  annote =	{Keywords: Object orientation, Datalog, query languages, prescriptive typing}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2016.13
Object Inheritance Without Classes

Authors: Timothy Jones, Michael Homer, James Noble, and Kim Bruce

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
Which comes first: the object or the class? Language designers enjoy the conceptual simplicity of object-based languages (such as Emerald or Self) while many programmers prefer the pragmatic utility of classical inheritance (as in Simula and Java). Programmers in object-based languages have a tendency to build libraries to support traditional inheritance, and language implementations are often contorted to the same end. In this paper, we revisit the relationship between classes and objects. We model various kinds of inheritance in the context of an object-oriented language whose objects are not defined by classes, and explain why class inheritance and initialisation cannot be easily modelled purely by delegation.
Cite as

Timothy Jones, Michael Homer, James Noble, and Kim Bruce. Object Inheritance Without Classes. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 13:1-13:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ECOOP.2016.13,
  author =	{Jones, Timothy and Homer, Michael and Noble, James and Bruce, Kim},
  title =	{{Object Inheritance Without Classes}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{13:1--13:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.13},
  URN =		{urn:nbn:de:0030-drops-61077},
  doi =		{10.4230/LIPIcs.ECOOP.2016.13},
  annote =	{Keywords: Inheritance, Objects, Classes, Operational semantics}
}
Document
DOI: 10.4230/DARTS.2.1.6
Object Inheritance Without Classes (Artifact)

Authors: Timothy Jones and Michael Homer

Published in: DARTS, Volume 2, Issue 1, Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
This artifact is a PLT Redex implementation of the operational semantics presented in Object Inheritance Without Classes. It defines the core syntax and runtime semantics of the Graceless language, and then extends it in multiple different ways to produce the various implementations of object inheritance, including single and multiple inheritance. The implementation makes the semantics runnable, and precisely defines some behaviour which is defined informally in the paper.
Cite as

Timothy Jones and Michael Homer. Object Inheritance Without Classes (Artifact). In Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016). Dagstuhl Artifacts Series (DARTS), Volume 2, Issue 1, pp. 6:1-6:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{jones_et_al:DARTS.2.1.6,
  author =	{Jones, Timothy and Homer, Michael},
  title =	{{Object Inheritance Without Classes (Artifact)}},
  pages =	{6:1--6:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2016},
  volume =	{2},
  number =	{1},
  editor =	{Jones, Timothy and Homer, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.2.1.6},
  URN =		{urn:nbn:de:0030-drops-61278},
  doi =		{10.4230/DARTS.2.1.6},
  annote =	{Keywords: Inheritance, Objects, Classes, Operational semantics, PLT Redex}
}
Document
DOI: 10.4230/DARTS.1.1.4
Brand Objects for Nominal Typing (Artifact)

Authors: Timothy Jones, Michael Homer, and James Noble

Published in: DARTS, Volume 1, Issue 1, Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
In Brand Objects for Nominal Typing, we describe an implementation of a branding system for both runtime and static types. This artifact provides the extended form of Hopper, an interpreter for the Grace programming language, and extra modules which define both the dynamic objects and the modular static type checker. The extra modules extend the existing structural type checker in the provided version of Hopper, and are capable of statically checking code which interacts with statically determinable declarations of brand objects, including singleton brand constructors, brand sums, and dynamic variables which are known to contain some brand value at runtime. The dynamic brand objects extend this behaviour to the runtime, enforcing non-static contracts and allowing runtime type testing.
Cite as

Timothy Jones, Michael Homer, and James Noble. Brand Objects for Nominal Typing (Artifact). In Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015). Dagstuhl Artifacts Series (DARTS), Volume 1, Issue 1, pp. 4:1-4:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{jones_et_al:DARTS.1.1.4,
  author =	{Jones, Timothy and Homer, Michael and Noble, James},
  title =	{{Brand Objects for Nominal Typing (Artifact)}},
  pages =	{4:1--4:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2015},
  volume =	{1},
  number =	{1},
  editor =	{Jones, Timothy and Homer, Michael and Noble, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.1.1.4},
  URN =		{urn:nbn:de:0030-drops-55134},
  doi =		{10.4230/DARTS.1.1.4},
  annote =	{Keywords: brands, types, structural, nominal, Grace}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2015.198
Brand Objects for Nominal Typing

Authors: Timothy Jones, Michael Homer, and James Noble

Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
Combinations of structural and nominal object typing in systems such as Scala, Whiteoak, and Unity have focused on extending existing nominal, class-based systems with structural subtyping. The typical rules of nominal typing do not lend themselves to such an extension, resulting in major modifications. Adding object branding to an existing structural system integrates nominal and structural typing without excessively complicating the type system. We have implemented brand objects to explicitly type objects, using existing features of the structurally typed language Grace, along with a static type checker which treats the brands as nominal types. We demonstrate that the brands are useful in an existing implementation of Grace, and provide a formal model of the extension to the language.
Cite as

Timothy Jones, Michael Homer, and James Noble. Brand Objects for Nominal Typing. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 198-221, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ECOOP.2015.198,
  author =	{Jones, Timothy and Homer, Michael and Noble, James},
  title =	{{Brand Objects for Nominal Typing}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{198--221},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.198},
  URN =		{urn:nbn:de:0030-drops-52314},
  doi =		{10.4230/LIPIcs.ECOOP.2015.198},
  annote =	{Keywords: brands, types, structural, nominal, Grace}
}
Document
DOI: 10.4230/OASIcs.ICCSW.2012.149
Introduction to Team Disruption Mechanisms

Authors: Andrada Voinitchi, Elizabeth Black, and Michael Luck

Published in: OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop

Abstract
This paper discusses how teams can be disrupted. More specifically, it discusses the steps that need to be taken in order to fully understand team disruption and design efficient mechanisms to disrupt teams. In order to answer the high-level question of how to disrupt teams, a few other questions need to be tackled first: what is a disrupted team? What are the crucial elements that make a collection of agents function as a team? Can norms, incentives or other mechanisms be used to disrupt these elements? How would we evaluate their efficiency? We first present the ideas of team and team disruption and motivate the need for these concepts to be properly defined. Secondly, we introduce an idea of team-disruption mechanism that we will further investigate. Lastly, we provide a long-term perspective and identify contributions that our research will make in the multi-agents field.
Cite as

Andrada Voinitchi, Elizabeth Black, and Michael Luck. Introduction to Team Disruption Mechanisms. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 149-155, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{voinitchi_et_al:OASIcs.ICCSW.2012.149,
  author =	{Voinitchi, Andrada and Black, Elizabeth and Luck, Michael},
  title =	{{Introduction to Team Disruption Mechanisms}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{149--155},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Jones, Andrew V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.149},
  URN =		{urn:nbn:de:0030-drops-37792},
  doi =		{10.4230/OASIcs.ICCSW.2012.149},
  annote =	{Keywords: Team disruption, multi-agent systems, organisations, teams, goals}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.229
Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average

Authors: Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stéphan Thomassé, and Anders Yeo

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
In the parameterized problem MaxLin2-AA[$k$], we are given a system with variables x_1,...,x_n consisting of equations of the form Product_{i in I}x_i = b, where x_i,b in {-1, 1} and I is a nonempty subset of {1,...,n}, each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (if k=0, the possibility is assured). We show that MaxLin2-AA[k] has a kernel with at most O(k^2 log k) variables and can be solved in time 2^{O(k log k)}(nm)^{O(1)}. This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove a theorem on Max-$r$-Lin2-AA[k,r] which implies that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables, improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function f that maps {-1,1}^n to the set of reals and whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erdös bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2 +(n-1)/4 edges) and obtaining a generalization.
Cite as

Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stéphan Thomassé, and Anders Yeo. Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 229-240, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2011.229,
  author =	{Crowston, Robert and Fellows, Michael and Gutin, Gregory and Jones, Mark and Rosamond, Frances and Thomass\'{e}, St\'{e}phan and Yeo, Anders},
  title =	{{Simultaneously Satisfying Linear Equations Over F\underline2: MaxLin2 and Max-r-Lin2 Parameterized Above Average}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{229--240},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.229},
  URN =		{urn:nbn:de:0030-drops-33416},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.229},
  annote =	{Keywords: MaxLin, fixed-parameter tractability, kernelization, pseudo-boolean functions}
}
Document
DOI: 10.4230/DagSemProc.07261.5
Better Ways to Cut a Cake - Revisited

Authors: Steven J. Brams, Michael A. Jones, and Christian Klamler

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
Procedures to divide a cake among n people with n-1 cuts (the minimum number) are analyzed and compared. For 2 persons, cut-and-choose, while envy-free and efficient, limits the cutter to exactly 50% if he or she is ignorant of the chooser's preferences, whereas the chooser can generally obtain more. By comparison, a new 2-person surplus procedure (SP'), which induces the players to be truthful in order to maximize their minimum allocations, leads to a proportionally equitable division of the surplus - the part that remains after each player receives 50% - by giving each person a certain proportion of the surplus as he or she values it. For n geq 3 persons, a new equitable procedure (EP) yields a maximally equitable division of a cake. This division gives all players the highest common value that they can achieve and induces truthfulness, but it may not be envy-free. The applicability of SP' and EP to the fair division of a heterogeneous, divisible good, like land, is briefly discussed.
Cite as

Steven J. Brams, Michael A. Jones, and Christian Klamler. Better Ways to Cut a Cake - Revisited. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.5,
  author =	{Brams, Steven J. and Jones, Michael A. and Klamler, Christian},
  title =	{{Better Ways to Cut a Cake - Revisited}},
  booktitle =	{Fair Division},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.5},
  URN =		{urn:nbn:de:0030-drops-12278},
  doi =		{10.4230/DagSemProc.07261.5},
  annote =	{Keywords: Fair division, cake-cutting, envy-freeness, strategy-proofness}
}
Document
DOI: 10.4230/DagSemProc.07261.6
Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure

Authors: Steven J. Brams, Michael A. Jones, and Christian Klamler

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
Properties of discrete cake-cutting procedures that use a minimal number of cuts (n-1 if there are n players) are analyzed. None is always envy-free or efficient, but divide-and-conquer (D&C) minimizes the maximum number of players that any single player may envy. It works by asking n ≥ 2 players successively to place marks on a cake that divide it into equal or approximately equal halves, then halves of these halves, and so on. Among other properties, D&C (i) ensures players of more than 1/n shares if their marks are different and (ii) is strategyproof for risk-averse players. However, D&C may not allow players to obtain proportional, connected pieces if they have unequal entitlements. Possible applications of D&C to land division are briefly discussed.
Cite as

Steven J. Brams, Michael A. Jones, and Christian Klamler. Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brams_et_al:DagSemProc.07261.6,
  author =	{Brams, Steven J. and Jones, Michael A. and Klamler, Christian},
  title =	{{Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure}},
  booktitle =	{Fair Division},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.6},
  URN =		{urn:nbn:de:0030-drops-12211},
  doi =		{10.4230/DagSemProc.07261.6},
  annote =	{Keywords: Cake-cutting, proportionality, envy-freeness, efficiency, strategy-proofness}
}
Document
DOI: 10.4230/DagSemProc.07261.11
Some Recent Results on Pie Cutting

Authors: Michael A. Jones

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
For cake cutting, cuts are parallel to an axis and yield rectangular pieces. As such, cutting a cake is viewed as dividing a line segment. For pie cutting, cuts are radial from the center of a disc to the circumference and yield sectors or wedge-shaped pieces. As such, cutting a pie is viewed as dividing a circle. There is clearly a relationship between cutting a cake and cutting a pie. Once a circular pie has a single cut, then it can be straightened out into a segment, looking like a cake. Isn't a cake just a pie that has been cut? Gale (1993) suggested that this topology was a significant difference. This note is to summarize and compare some of the recent results on pie cutting that appear in Barbanel and Brams (2007) and Brams, Jones, and Klamler (2007). The geometric framework presented in Barbanel and Brams (2007) is used to prove and to explain results in Brams, Jones, and Klamler (2007).
Cite as

Michael A. Jones. Some Recent Results on Pie Cutting. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{jones:DagSemProc.07261.11,
  author =	{Jones, Michael A.},
  title =	{{Some Recent Results on Pie Cutting}},
  booktitle =	{Fair Division},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.11},
  URN =		{urn:nbn:de:0030-drops-12246},
  doi =		{10.4230/DagSemProc.07261.11},
  annote =	{Keywords: Pie cutting, envy-free, proportional, undominated}
}
  • Refine by Author
  • 4 Homer, Michael
  • 4 Jones, Timothy
  • 3 Jones, Michael A.
  • 3 Noble, James
  • 2 Brams, Steven J.
  • Show More...

  • Refine by Classification
  • 2 Computer systems organization → Embedded and cyber-physical systems
  • 1 Hardware → Model checking
  • 1 Hardware → Redundancy
  • 1 Hardware → Theorem proving and SAT solving
  • 1 Information systems → Data centers
  • Show More...

  • Refine by Keyword
  • 2 Classes
  • 2 Grace
  • 2 Inheritance
  • 2 Objects
  • 2 Operational semantics
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 3 2007
  • 3 2016
  • 2 2015
  • 1 2011
  • 1 2012
  • 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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact