Search

Your search keyword '"Widmayer, Peter"' showing total 1,241 results
Start Over Author "Widmayer, Peter"

Refine your results

more »

more »

more »

more »
1,241 results on '"Widmayer, Peter"'

1. Bribeproof mechanisms for two-values domains

Author

Mihalák, Matúš, Penna, Paolo, and Widmayer, Peter

Subjects
Computer Science - Computer Science and Game Theory
Abstract

Schummer (Journal of Economic Theory 2000) introduced the concept of bribeproof mechanism which, in a context where monetary transfer between agents is possible, requires that manipulations through bribes are ruled out. Unfortunately, in many domains, the only bribeproof mechanisms are the trivial ones which return a fixed outcome. This work presents one of the few constructions of non-trivial bribeproof mechanisms for these quasi-linear environments. Though the suggested construction applies to rather restricted domains, the results obtained are tight: For several natural problems, the method yields the only possible bribeproof mechanism and no such mechanism is possible on more general domains., Comment: Extended abstract accepted to SAGT 2016. This ArXiv version corrects typos in the proofs of Theorem 7 and Claims 28-29 of prior ArXiv version

Published
2015

4. Anhang

Author

Ottmann, Thomas, Widmayer, Peter, Ottmann, Thomas, and Widmayer, Peter

Published
2018
Full Text
View/download PDF

11. Counting approximately-shortest paths in directed acyclic graphs

Author

Mihalák, Matúš, Šrámek, Rastislav, and Widmayer, Peter

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most L. We extend the algorithm for the case of two (or more) instances of the same problem. That is, given two graphs that have the same vertices and edges and differ only in edge-weights, and given two threshold-weights L_1 and L_2, we show how to approximately count the s-t paths that have length at most L_1 in the first graph and length at most L_2 in the second graph. We believe that our algorithms should find application in counting approximate solutions of related optimization problems, where finding an (optimum) solution can be reduced to the computation of a shortest path in a purpose-built auxiliary graph.

Published
2013

12. Simple Agents Learn to Find Their Way: An Introduction on Mapping Polygons

Author

Chalopin, Jérémie, Das, Shantanu, Disser, Yann, Mihalák, Matúš, and Widmayer, Peter

Subjects
Computer Science - Computational Geometry
Abstract

This paper gives an introduction to the problem of mapping simple polygons with autonomous agents. We focus on minimalistic agents that move from vertex to vertex along straight lines inside a polygon, using their sensors to gather local observations at each vertex. Our attention revolves around the question whether a given configuration of sensors and movement capabilities of the agents allows them to capture enough data in order to draw conclusions regarding the global layout of the polygon. In particular, we study the problem of reconstructing the visibility graph of a simple polygon by an agent moving either inside or on the boundary of the polygon. Our aim is to provide insight about the algorithmic challenges faced by an agent trying to map a polygon. We present an overview of techniques for solving this problem with agents that are equipped with simple sensorial capabilities. We illustrate these techniques on examples with sensors that mea- sure angles between lines of sight or identify the previous location. We give an overview over related problems in combinatorial geometry as well as graph exploration.

Published
2012
Full Text
View/download PDF

18. Bäume

Author

Ottmann, Thomas, Widmayer, Peter, Ottmann, Thomas, and Widmayer, Peter

Published
2017
Full Text
View/download PDF

20. Sortieren

Author

Ottmann, Thomas, Widmayer, Peter, Ottmann, Thomas, and Widmayer, Peter

Published
2017
Full Text
View/download PDF

22. Sequence Hypergraphs: Paths, Flows, and Cuts

Author

Böhmová, Kateřina, Chalopin, Jérémie, Mihalák, Matúš, Proietti, Guido, Widmayer, Peter, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Böckenhauer, Hans-Joachim, editor, Komm, Dennis, editor, and Unger, Walter, editor

Published
2018
Full Text
View/download PDF

23. Sequence Hypergraphs

Author

Böhmová, Kateřina, Chalopin, Jérémie, Mihalák, Matúš, Proietti, Guido, Widmayer, Peter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Heggernes, Pinar, editor

Published
2016
Full Text
View/download PDF

24. Bribeproof Mechanisms for Two-Values Domains

Author

Mihalák, Matúš, Penna, Paolo, Widmayer, Peter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gairing, Martin, editor, and Savani, Rahul, editor

Published
2016
Full Text
View/download PDF

25. A Better Scoring Model for De Novo Peptide Sequencing: The Symmetric Difference Between Explained and Measured Masses

Author

Gillet, Ludovic, Rösch, Simon, Tschager, Thomas, Widmayer, Peter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Frith, Martin, editor, and Storm Pedersen, Christian Nørgaard, editor

Published
2016
Full Text
View/download PDF

30. Bäume

Author

Ottmann, Thomas, Widmayer, Peter, Ottmann, Thomas, and Widmayer, Peter

Published
2012
Full Text
View/download PDF

32. Suchen

Author

Ottmann, Thomas, Widmayer, Peter, Ottmann, Thomas, and Widmayer, Peter

Published
2012
Full Text
View/download PDF

35. Recurring Comparison Faults: Sorting and Finding the Minimum

Author

Geissmann, Barbara, Mihalák, Matúš, Widmayer, Peter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kosowski, Adrian, editor, and Walukiewicz, Igor, editor

Published
2015
Full Text
View/download PDF

36. Data Delivery by Energy-Constrained Mobile Agents on a Line

Author

Chalopin, Jérémie, Jacob, Riko, Mihalák, Matúš, Widmayer, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Esparza, Javier, editor, Fraigniaud, Pierre, editor, Husfeldt, Thore, editor, and Koutsoupias, Elias, editor

Published
2014
Full Text
View/download PDF

38. Polygon-Constrained Motion Planning Problems

Author

Bilò, Davide, Disser, Yann, Gualà, Luciano, Mihal’ák, Matúš, Proietti, Guido, Widmayer, Peter, Flocchini, Paola, editor, Gao, Jie, editor, Kranakis, Evangelos, editor, and Meyer auf der Heide, Friedhelm, editor

Published
2014
Full Text
View/download PDF

39. Rectilinear Shortest Path and Rectilinear Minimum Spanning Tree with Neighborhoods

Author

Disser, Yann, Mihalák, Matúš, Montanari, Sandro, Widmayer, Peter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Fouilhoux, Pierre, editor, Gouveia, Luis Eduardo Neves, editor, Mahjoub, A. Ridha, editor, and Paschos, Vangelis T., editor

Published
2014
Full Text
View/download PDF

40. Counting Approximately-Shortest Paths in Directed Acyclic Graphs

Author

Mihalák, Matúš, Šrámek, Rastislav, Widmayer, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Kaklamanis, Christos, editor, and Pruhs, Kirk, editor

Published
2014
Full Text
View/download PDF

41. Anhang

Author

Ottmann, Thomas, Widmayer, Peter, Ottmann, Thomas, and Widmayer, Peter

Published
2003
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results