Search Results

Documents authored by Dyer, Martin E.

Found 2 Possible Name Variants:

Dyer, Martin E.

Document
DOI: 10.4230/DagSemProc.08201.1
08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms

Authors: Martin E. Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Proceedings, Volume 8201, Design and Analysis of Randomized and Approximation Algorithms (2008)

Abstract
From 11.05.08 to 16.05.08, the Dagstuhl Seminar 08201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research work, and ongoing work and open problems were discussed. Abstracts of the presentations which were given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full paper are provided, if available.
Cite as

Martin E. Dyer, Mark Jerrum, and Marek Karpinski. 08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 8201, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:DagSemProc.08201.1,
  author =	{Dyer, Martin E. and Jerrum, Mark and Karpinski, Marek},
  title =	{{08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}},
  booktitle =	{Design and Analysis of Randomized and Approximation Algorithms},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8201},
  editor =	{Martin E. Dyer and Mark Jerrum and Marek Karpinski},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08201.1},
  URN =		{urn:nbn:de:0030-drops-15518},
  doi =		{10.4230/DagSemProc.08201.1},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Approximation Complexity, Algorithmic Game Theory, Internet, Decentralized Networks, Network Design}
}

Dyer, Martin

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.66
A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights

Authors: Artem Govorov, Jin-Yi Cai, and Martin Dyer

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z_A(⋅), also known as the partition function. Dyer and Greenhill [Martin E. Dyer and Catherine S. Greenhill, 2000] established a complexity dichotomy of Z_A(⋅) for symmetric {0, 1}-matrices A, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [Andrei Bulatov and Martin Grohe, 2005] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices A. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric A, either Z_A(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [Leslie A. Goldberg et al., 2010] for Z_A(⋅) also holds for simple graphs, where A is any real symmetric matrix.
Cite as

Artem Govorov, Jin-Yi Cai, and Martin Dyer. A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{govorov_et_al:LIPIcs.ICALP.2020.66,
  author =	{Govorov, Artem and Cai, Jin-Yi and Dyer, Martin},
  title =	{{A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{66:1--66:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.66},
  URN =		{urn:nbn:de:0030-drops-124733},
  doi =		{10.4230/LIPIcs.ICALP.2020.66},
  annote =	{Keywords: Graph homomorphism, Complexity dichotomy, Counting problems}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.145
Discordant Voting Processes on Finite Graphs

Authors: Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus, i.e. the number of interactions needed for all vertices have the same colour. An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. - Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. - Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. - Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point. We show that ET, the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, ET = (n^2)/4 independent of the underlying graph. For the complete graph Kn, the push protocol has ET = Theta(n*log(n)), whereas the pull protocol has ET = Theta(2^n). For the cycle C_n all three protocols have ET = Theta(n^2). For the star graph however, the pull protocol has ET = O(n^2), whereas the push protocol is slower with ET = Theta(n^2*log(n)). The wide variation in ET for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which ET = O(n) on many classes of expanders.
Cite as

Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera. Discordant Voting Processes on Finite Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 145:1-145:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.ICALP.2016.145,
  author =	{Cooper, Colin and Dyer, Martin and Frieze, Alan and Rivera, Nicol\'{a}s},
  title =	{{Discordant Voting Processes on Finite Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{145:1--145:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.145},
  URN =		{urn:nbn:de:0030-drops-62898},
  doi =		{10.4230/LIPIcs.ICALP.2016.145},
  annote =	{Keywords: Distributed consensus, Voter model, Interacting particles, Randomized algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.148
The complexity of approximating conservative counting CSPs

Authors: Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We study the complexity of approximation for a weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, a classification is known for the Boolean domain. We give a classification for problems with general finite domain. We define weak log-modularity and weak log-supermodularity, and show that #CSP(F) is in FP if F is weakly log-modular. Otherwise, it is at least as hard to approximate as #BIS, counting independent sets in bipartite graphs, which is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, we show that #CSP(F) is as easy as Boolean log-supermodular weighted #CSP. Otherwise, it is NP-hard to approximate. Finally, we give a trichotomy for the arity-2 case. Then, #CSP(F) is in FP, is #BIS-equivalent, or is equivalent to #SAT, the problem of approximately counting satisfying assignments of a CNF Boolean formula.
Cite as

Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 148-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2013.148,
  author =	{Chen, Xi and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark and Lu, Pinyan and McQuillan, Colin and Richerby, David},
  title =	{{The complexity of approximating conservative counting CSPs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{148--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.148},
  URN =		{urn:nbn:de:0030-drops-39303},
  doi =		{10.4230/LIPIcs.STACS.2013.148},
  annote =	{Keywords: counting constraint satisfaction problem, approximation, complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.302
Log-supermodular functions, functional clones and counting CSPs

Authors: Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Motivated by a desire to understand the computational complexity of counting constraint satisfaction problems (counting CSPs), particularly the complexity of approximation, we study functional clones of functions on the Boolean domain, which are analogous to the familiar relational clones constituting Post's lattice. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In our study, we assume that non-negative unary functions (weights) are available. Given this, we prove that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard as any problem in #P. Furthermore, any non-trivial functional clone (in a sense that will be made precise below) contains the binary function "implies". As a consequence, all non-trivial counting CSPs (with non-negative unary weights assumed to be available) are computationally at least as difficult as #BIS, the problem of counting independent sets in a bipartite graph. There is empirical evidence that #BIS is hard to solve, even approximately.
Cite as

Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 302-313, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2012.302,
  author =	{Bulatov, Andrei A. and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{Log-supermodular functions, functional clones and counting CSPs}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{302--313},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.302},
  URN =		{urn:nbn:de:0030-drops-34078},
  doi =		{10.4230/LIPIcs.STACS.2012.302},
  annote =	{Keywords: counting constraint satisfaction problems, approximation, complexity}
}
Document
DOI: 10.4230/DagRep.1.6.24
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)

Authors: Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski

Published in: Dagstuhl Reports, Volume 1, Issue 6 (2011)

Abstract
The Dagstuhl Seminar on ``Design and Analysis of Randomized and Approximation Algorithms'' (Seminar 11241) was held at Schloss Dagstuhl between June 13--17, 2011. There were 26 regular talks and several informal and open problem session contributions presented during this seminar. Abstracts of the presentations have been put together in this seminar proceedings document together with some links to extended abstracts and full papers.
Cite as

Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). In Dagstuhl Reports, Volume 1, Issue 6, pp. 24-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{dyer_et_al:DagRep.1.6.24,
  author =	{Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek},
  title =	{{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)}},
  pages =	{24--53},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{6},
  editor =	{Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.6.24},
  URN =		{urn:nbn:de:0030-drops-32585},
  doi =		{10.4230/DagRep.1.6.24},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Probabilistically Checkable Proofs, Approximation Hardness, Optimization Problems, Counting Problems, Streaming Algorithms, Random Graphs, Hypergraphs, Probabilistic Method, Networks, Linear Programs, Semidefinite Programs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.261
The #CSP Dichotomy is Decidable

Authors: Martin Dyer and David Richerby

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Bulatov (2008) and Dyer and Richerby (2010) have established the following dichotomy for the counting constraint satisfaction problem (#CSP): for any constraint language Gamma, the problem of computing the number of satisfying assignments to constraints drawn from Gamma is either in FP or is #P-complete, depending on the structure of Gamma. The principal question left open by this research was whether the criterion of the dichotomy is decidable. We show that it is; in fact, it is in NP.
Cite as

Martin Dyer and David Richerby. The #CSP Dichotomy is Decidable. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 261-272, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:LIPIcs.STACS.2011.261,
  author =	{Dyer, Martin and Richerby, David},
  title =	{{The #CSP Dichotomy is Decidable}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{261--272},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.261},
  URN =		{urn:nbn:de:0030-drops-30161},
  doi =		{10.4230/LIPIcs.STACS.2011.261},
  annote =	{Keywords: constraint satisfaction problem, counting problems, complexity dichotomy, decidability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2466
The Complexity of Approximating Bounded-Degree Boolean #CSP

Authors: Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, and David Richerby

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations $\{0\}$ and $\{1\}$. When the maximum degree is at least $25$ we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of $\{0\}$, $\{1\}$ and binary implication. Otherwise, there is no FPRAS unless $\NPtime = \RPtime$. For lower degree bounds, additional cases arise in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.
Cite as

Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, and David Richerby. The Complexity of Approximating Bounded-Degree Boolean #CSP. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 323-334, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:LIPIcs.STACS.2010.2466,
  author =	{Dyer, Martin and Goldberg, Leslie Ann and Jalsenius, Markus and Richerby, David},
  title =	{{The Complexity of Approximating Bounded-Degree Boolean #CSP}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{323--334},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2466},
  URN =		{urn:nbn:de:0030-drops-24669},
  doi =		{10.4230/LIPIcs.STACS.2010.2466},
  annote =	{Keywords: Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.05201.1
05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms

Authors: Martin Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Proceedings, Volume 5201, Design and Analysis of Randomized and Approximation Algorithms (2005)

Abstract
From 15.05.05 to 20.05.05, the Dagstuhl Seminar 05201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Martin Dyer, Mark Jerrum, and Marek Karpinski. 05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 5201, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:DagSemProc.05201.1,
  author =	{Dyer, Martin and Jerrum, Mark and Karpinski, Marek},
  title =	{{05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}},
  booktitle =	{Design and Analysis of Randomized and Approximation Algorithms},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5201},
  editor =	{Martin Dyer and Mark Jerrum and Marek Karpinski},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05201.1},
  URN =		{urn:nbn:de:0030-drops-3191},
  doi =		{10.4230/DagSemProc.05201.1},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Decentralized Networks}
}
Document
DOI: 10.4230/DagSemRep.309
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231)

Authors: Martin Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Martin Dyer, Mark Jerrum, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231). Dagstuhl Seminar Report 309, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{dyer_et_al:DagSemRep.309,
  author =	{Dyer, Martin and Jerrum, Mark and Karpinski, Marek},
  title =	{{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{309},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.309},
  URN =		{urn:nbn:de:0030-drops-151930},
  doi =		{10.4230/DagSemRep.309},
}
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