4 Search Results for "Crowston, Robert"


Document
Engineering Academic Software (Dagstuhl Perspectives Workshop 16252)

Authors: Alice Allen, Cecilia Aragon, Christoph Becker, Jeffrey Carver, Andrei Chis, Benoit Combemale, Mike Croucher, Kevin Crowston, Daniel Garijo, Ashish Gehani, Carole Goble, Robert Haines, Robert Hirschfeld, James Howison, Kathryn Huff, Caroline Jay, Daniel S. Katz, Claude Kirchner, Katie Kuksenok, Ralf Lämmel, Oscar Nierstrasz, Matt Turk, Rob van Nieuwpoort, Matthew Vaughn, and Jurgen J. Vinju

Published in: Dagstuhl Manifestos, Volume 6, Issue 1 (2017)


Abstract
Software is often a critical component of scientific research. It can be a component of the academic research methods used to produce research results, or it may itself be an academic research result. Software, however, has rarely been considered to be a citable artifact in its own right. With the advent of open-source software, artifact evaluation committees of conferences, and journals that include source code and running systems as part of the published artifacts, we foresee that software will increasingly be recognized as part of the academic process. The quality and sustainability of this software must be accounted for, both a prioro and a posteriori. The Dagstuhl Perspectives Workshop on "Engineering Academic Software" has examined the strengths, weaknesses, risks, and opportunities of academic software engineering. A key outcome of the workshop is this Dagstuhl Manifesto, serving as a roadmap towards future professional software engineering for software-based research instruments and other software produced and used in an academic context. The manifesto is expressed in terms of a series of actionable "pledges" that users and developers of academic research software can take as concrete steps towards improving the environment in which that software is produced.

Cite as

Alice Allen, Cecilia Aragon, Christoph Becker, Jeffrey Carver, Andrei Chis, Benoit Combemale, Mike Croucher, Kevin Crowston, Daniel Garijo, Ashish Gehani, Carole Goble, Robert Haines, Robert Hirschfeld, James Howison, Kathryn Huff, Caroline Jay, Daniel S. Katz, Claude Kirchner, Katie Kuksenok, Ralf Lämmel, Oscar Nierstrasz, Matt Turk, Rob van Nieuwpoort, Matthew Vaughn, and Jurgen J. Vinju. Engineering Academic Software (Dagstuhl Perspectives Workshop 16252). In Dagstuhl Manifestos, Volume 6, Issue 1, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{allen_et_al:DagMan.6.1.1,
  author =	{Allen, Alice and Aragon, Cecilia and Becker, Christoph and Carver, Jeffrey and Chis, Andrei and Combemale, Benoit and Croucher, Mike and Crowston, Kevin and Garijo, Daniel and Gehani, Ashish and Goble, Carole and Haines, Robert and Hirschfeld, Robert and Howison, James and Huff, Kathryn and Jay, Caroline and Katz, Daniel S. and Kirchner, Claude and Kuksenok, Katie and L\"{a}mmel, Ralf and Nierstrasz, Oscar and Turk, Matt and van Nieuwpoort, Rob and Vaughn, Matthew and Vinju, Jurgen J.},
  title =	{{Engineering Academic Software (Dagstuhl Perspectives Workshop 16252)}},
  pages =	{1--20},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2017},
  volume =	{6},
  number =	{1},
  editor =	{Allen, Alice and Aragon, Cecilia and Becker, Christoph and Carver, Jeffrey and Chis, Andrei and Combemale, Benoit and Croucher, Mike and Crowston, Kevin and Garijo, Daniel and Gehani, Ashish and Goble, Carole and Haines, Robert and Hirschfeld, Robert and Howison, James and Huff, Kathryn and Jay, Caroline and Katz, Daniel S. and Kirchner, Claude and Kuksenok, Katie and L\"{a}mmel, Ralf and Nierstrasz, Oscar and Turk, Matt and van Nieuwpoort, Rob and Vaughn, Matthew and Vinju, Jurgen J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.6.1.1},
  URN =		{urn:nbn:de:0030-drops-71468},
  doi =		{10.4230/DagMan.6.1.1},
  annote =	{Keywords: Academic software, Research software, Software citation, Software sustainability}
}
Document
Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound

Authors: Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh

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


Abstract
Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<lambda<1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda*m+(1-lambda)(n-1)/2 edges. The property of being bipartite is lambda-extendible for lambda =1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max Cut. Other examples of lambda-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some q in N. Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambda-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambda-extendible property Pi is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound---does there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1-lambda)(n-1)/2+k edges?---subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambda-extendible properties which satisfy the additional criterion. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when lambda=1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.

Cite as

Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2013.43,
  author =	{Crowston, Robert and Jones, Mark and Muciaccia, Gabriele and Philip, Geevarghese and Rai, Ashutosh and Saurabh, Saket},
  title =	{{Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{43--54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.43},
  URN =		{urn:nbn:de:0030-drops-43599},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.43},
  annote =	{Keywords: Kernelization, Lambda Extension, Above-Guarantee Parameterization, MaxCut}
}
Document
Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound

Authors: Robert Crowston, Gregory Gutin, and Mark Jones

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


Abstract
An oriented graph is a directed graph without directed 2-cycles. Poljak and Turzik (1986) proved that every connected oriented graph G on n vertices and m arcs contains an acyclic subgraph with at least m/2+(n-1)/4 arcs. Raman and Saurabh (2006) gave another proof of this result and left it as an open question to establish the parameterized complexity of the following problem: does G have an acyclic subgraph with least m/2 + (n-1)/4 + k arcs, where k is the parameter? We answer this question by showing that the problem can be solved by an algorithm of runtime (12k)!n^{O(1)}. Thus, the problem is fixed-parameter tractable. We also prove that there is a polynomial time algorithm that either establishes that the input instance of the problem is a Yes-instance or reduces the input instance to an equivalent one of size O(k^2).

Cite as

Robert Crowston, Gregory Gutin, and Mark Jones. Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 400-411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2012.400,
  author =	{Crowston, Robert and Gutin, Gregory and Jones, Mark},
  title =	{{Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{400--411},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.400},
  URN =		{urn:nbn:de:0030-drops-38765},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.400},
  annote =	{Keywords: Acyclic Subgraph, Fixed-parameter tractable, Polynomial Kernel}
}
Document
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-dev.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}
}
  • Refine by Author
  • 3 Crowston, Robert
  • 3 Jones, Mark
  • 2 Gutin, Gregory
  • 1 Allen, Alice
  • 1 Aragon, Cecilia
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Above-Guarantee Parameterization
  • 1 Academic software
  • 1 Acyclic Subgraph
  • 1 Fixed-parameter tractable
  • 1 Kernelization
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2011
  • 1 2012
  • 1 2013
  • 1 2017

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