9 Search Results for "Peters, J�rg"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.10
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems

Authors: Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz

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

Abstract
We study the question of when an approximate search optimization problem is harder than the associated decision problem. Specifically, we study a natural and quite general model of black-box search-to-decision reductions, which we call branch-and-bound reductions (in analogy with branch-and-bound algorithms). In this model, an algorithm attempts to minimize (or maximize) a function f: D → ℝ_{≥ 0} by making oracle queries to h_f : 𝒮 → ℝ_{≥ 0} satisfying min_{x ∈ S} f(x) ≤ h_f(S) ≤ γ ⋅ min_{x ∈ S} f(x) (*) for some γ ≥ 1 and any subset S in some allowed class of subsets 𝒮 of the domain D. (When the goal is to maximize f, h_f instead yields an approximation to the maximal value of f over S.) We show tight upper and lower bounds on the number of queries q needed to find even a γ'-approximate minimizer (or maximizer) for quite large γ' in a number of interesting settings, as follows. - For arbitrary functions f : {0,1}ⁿ → ℝ_{≥ 0}, where 𝒮 contains all subsets of the domain, we show that no branch-and-bound reduction can achieve γ' ≲ γ^{n/log q}, while a simple greedy approach achieves essentially γ^{n/log q}. - For a large class of MAX-CSPs, where 𝒮 := {S_w} contains each set of assignments to the variables induced by a partial assignment w, we show that no branch-and-bound reduction can do significantly better than essentially a random guess, even when the oracle h_f guarantees an approximation factor of γ ≈ 1+√{log(q)/n}. - For the Traveling Salesperson Problem (TSP), where 𝒮 := {S_p} contains each set of tours extending a path p, we show that no branch-and-bound reduction can achieve γ' ≲ (γ-1) n/log q. We also prove a nearly matching upper bound in our model. These results show an oracle model in which approximate search and decision are strongly separated. (In particular, our result for TSP can be viewed as a negative answer to a question posed by Bellare and Goldwasser (SIAM J. Comput. 1994), though only in an oracle model.) We also note two alternative interpretations of our results. First, if we view h_f as a data structure, then our results unconditionally rule out black-box search-to-decision reductions for certain data structure problems. Second, if we view h_f as an efficiently computable heuristic, then our results show that any reasonably efficient branch-and-bound algorithm requires more guarantees from its heuristic than simply Eq. (*). Behind our results is a "useless oracle lemma," which allows us to argue that under certain conditions the oracle h_f is "useless," and which might be of independent interest. See also the full version [Alexander Golovnev et al., 2022].
Cite as

Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz. The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2023.10,
  author =	{Golovnev, Alexander and Guo, Siyao and Peters, Spencer and Stephens-Davidowitz, Noah},
  title =	{{The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  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.2023.10},
  URN =		{urn:nbn:de:0030-drops-188351},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.10},
  annote =	{Keywords: search-to-decision reductions, oracles, constraint satisfaction, traveling salesman, discrete optimization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.41
Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities

Authors: Tom Demeulemeester and Jannik Peters

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study relationships between different relaxed notions of core stability in hedonic games. In particular, we study (i) q-size core stable outcomes in which no deviating coalition of size at most q exists and (ii) k-improvement core stable outcomes in which no coalition can improve by a factor of more than k. For a large class of hedonic games, including fractional and additively separable hedonic games, we derive upper bounds on the maximum factor by which a coalition of a certain size can improve in a q-size core stable outcome. We further provide asymptotically tight lower bounds for a large class of hedonic games. Finally, our bounds allow us to confirm two conjectures by Fanelli et al. [Angelo Fanelli et al., 2021][IJCAI'21] for symmetric fractional hedonic games (S-FHGs): (i) every q-size core stable outcome in an S-FHG is also q/(q-1)-improvement core stable and (ii) the price of anarchy of q-size stability in S-FHGs is precisely 2q/q-1.
Cite as

Tom Demeulemeester and Jannik Peters. Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{demeulemeester_et_al:LIPIcs.MFCS.2023.41,
  author =	{Demeulemeester, Tom and Peters, Jannik},
  title =	{{Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.41},
  URN =		{urn:nbn:de:0030-drops-185759},
  doi =		{10.4230/LIPIcs.MFCS.2023.41},
  annote =	{Keywords: hedonic games, core stability, algorithmic game theory, computational social choice}
}
Document
DOI: 10.4230/DagRep.9.12.115
Interactive Design and Simulation (Dagstuhl Seminar 19512)

Authors: Thomas A. Grandine, Jörg Peters, and Ulrich Reif

Published in: Dagstuhl Reports, Volume 9, Issue 12 (2020)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19512 ""Interactive Design and Simulation". After the executive summary, the collection of abstracts of the presentations forms the core of this report, complemented by an example of working group results that highlights the diversity of backgrounds and approaches.
Cite as

Thomas A. Grandine, Jörg Peters, and Ulrich Reif. Interactive Design and Simulation (Dagstuhl Seminar 19512). In Dagstuhl Reports, Volume 9, Issue 12, pp. 115-134, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{grandine_et_al:DagRep.9.12.115,
  author =	{Grandine, Thomas A. and Peters, J\"{o}rg and Reif, Ulrich},
  title =	{{Interactive Design and Simulation (Dagstuhl Seminar 19512)}},
  pages =	{115--134},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{9},
  number =	{12},
  editor =	{Grandine, Thomas A. and Peters, J\"{o}rg and Reif, Ulrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.12.115},
  URN =		{urn:nbn:de:0030-drops-120120},
  doi =		{10.4230/DagRep.9.12.115},
  annote =	{Keywords: simulation of physical systems, geometric models for engineering analysis, partial differential equations, interactive and real-time computation splines, model reduction}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.63
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs

Authors: J. Ian Munro and Sebastian Wild

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

Abstract
We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with negligible overhead. Previous methods either require substantial effort for determining the merging order (Takaoka 2009; Barbay & Navarro 2013) or do not have an optimal worst-case guarantee (Peters 2002; Auger, Nicaud & Pivoteau 2015; Buss & Knop 2018) . We demonstrate that our methods are competitive in terms of running time with state-of-the-art implementations of stable sorting methods.
Cite as

J. Ian Munro and Sebastian Wild. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{munro_et_al:LIPIcs.ESA.2018.63,
  author =	{Munro, J. Ian and Wild, Sebastian},
  title =	{{Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{63:1--63:16},
  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.63},
  URN =		{urn:nbn:de:0030-drops-95265},
  doi =		{10.4230/LIPIcs.ESA.2018.63},
  annote =	{Keywords: adaptive sorting, nearly-optimal binary search trees, Timsort}
}
Document
DOI: 10.4230/DagRep.1.5.84
Geometric Modeling (Dagstuhl Seminar 11211)

Authors: Thomas A. Grandine, Stefanie Hahmann, Jörg Peters, and Wenping Wang

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

Abstract
This report documents the program and the results of Dagstuhl Seminar 11211 ``Geometric Modeling'', taking place May 22-27 2011. The focus of the seminar was to discuss modern and emerging topics in Geometric Modeling by researchers and industrial scientists from all over the world.
Cite as

Thomas A. Grandine, Stefanie Hahmann, Jörg Peters, and Wenping Wang. Geometric Modeling (Dagstuhl Seminar 11211). In Dagstuhl Reports, Volume 1, Issue 5, pp. 84-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{grandine_et_al:DagRep.1.5.84,
  author =	{Grandine, Thomas A. and Hahmann, Stefanie and Peters, J\"{o}rg and Wang, Wenping},
  title =	{{Geometric Modeling (Dagstuhl Seminar 11211)}},
  pages =	{84--107},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{5},
  editor =	{Grandine, Thomas A. and Hahmann, Stefanie and Peters, J\"{o}rg and Wang, Wenping},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.5.84},
  URN =		{urn:nbn:de:0030-drops-32132},
  doi =		{10.4230/DagRep.1.5.84},
  annote =	{Keywords: Geometric modeling, design, curve and surface modeling, splines, CAD, B-splines, reconstruction, subdivision methods, multiresolution, parameterization}
}
Document
DOI: 10.4230/DagSemProc.08221.1
08221 Abstracts Collection – Geometric Modeling

Authors: Gerald Farin, Stefanie Hahmann, Jörg Peters, and Wenping Wang

Published in: Dagstuhl Seminar Proceedings, Volume 8221, Geometric Modeling (2008)

Abstract
From May 26 to May 30 2008 the Dagstuhl Seminar 08221 ``Geometric Modeling'' 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

Gerald Farin, Stefanie Hahmann, Jörg Peters, and Wenping Wang. 08221 Abstracts Collection – Geometric Modeling. In Geometric Modeling. Dagstuhl Seminar Proceedings, Volume 8221, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{farin_et_al:DagSemProc.08221.1,
  author =	{Farin, Gerald and Hahmann, Stefanie and Peters, J\"{o}rg and Wang, Wenping},
  title =	{{08221 Abstracts Collection – Geometric Modeling}},
  booktitle =	{Geometric Modeling},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8221},
  editor =	{Gerald Farin and Stefanie Hahmann and J\"{o}rg Peters and Wenping Wang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08221.1},
  URN =		{urn:nbn:de:0030-drops-15381},
  doi =		{10.4230/DagSemProc.08221.1},
  annote =	{Keywords: Geometry, engineering, volumetric modeling, computer graphics}
}
Document
DOI: 10.4230/DagSemProc.08221.2
08221 Summary – Geometric Modeling

Authors: Gerald Farin, Stefanie Hahmann, Jörg Peters, and Wenping Wang

Published in: Dagstuhl Seminar Proceedings, Volume 8221, Geometric Modeling (2008)

Abstract
Geometric Modeling is an area drawing from computer science, mathematics, engineering, and the life sciences. It is concerned with the computer representation of objects as diverse as - brain scans - mathematical functions - terrains - airplane wings and many more. The seminar succeeded in bringing together leading researchers to present and discuss radically different approaches to the challenge of modeling complex geometric phenomena on the computer. Acquisition, representation and analysis of 3-dimensional geometry call for the combination of technically complex and often interdisciplinary approaches that are grounded both in classical mathematics and computer science data structures and theory.
Cite as

Gerald Farin, Stefanie Hahmann, Jörg Peters, and Wenping Wang. 08221 Summary – Geometric Modeling. In Geometric Modeling. Dagstuhl Seminar Proceedings, Volume 8221, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{farin_et_al:DagSemProc.08221.2,
  author =	{Farin, Gerald and Hahmann, Stefanie and Peters, J\"{o}rg and Wang, Wenping},
  title =	{{08221 Summary – Geometric Modeling}},
  booktitle =	{Geometric Modeling},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8221},
  editor =	{Gerald Farin and Stefanie Hahmann and J\"{o}rg Peters and Wenping Wang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08221.2},
  URN =		{urn:nbn:de:0030-drops-15379},
  doi =		{10.4230/DagSemProc.08221.2},
  annote =	{Keywords: Geometry, engineering, volumetric modeling, computer graphics}
}
Document
DOI: 10.4230/DagSemProc.06021.5
Floating Point Geometric Algorithms for Topologically Correct Scientific Visualization

Authors: Thomas J. Peters and Edward L. F. Moore

Published in: Dagstuhl Seminar Proceedings, Volume 6021, Reliable Implementation of Real Number Algorithms: Theory and Practice (2006)

Abstract
The unresolved subtleties of floating point computations in geometric modeling become considerably more difficult in animations and scientific visualizations. Some emerging solutions based upon topological considerations will be presented. A novel geometric seeding algorithm for Newton's method was used in experiments to determine feasible support for these visualization applications.
Cite as

Thomas J. Peters and Edward L. F. Moore. Floating Point Geometric Algorithms for Topologically Correct Scientific Visualization. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{peters_et_al:DagSemProc.06021.5,
  author =	{Peters, Thomas J. and Moore, Edward L. F.},
  title =	{{Floating Point Geometric Algorithms for Topologically Correct Scientific Visualization}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.5},
  URN =		{urn:nbn:de:0030-drops-7176},
  doi =		{10.4230/DagSemProc.06021.5},
  annote =	{Keywords: Geometry, algorithm, visualization}
}
Document
DOI: 10.4230/DagSemProc.04351.16
Integrating Topology and Geometry for Macro-Molecular Simulations

Authors: Edward L. F. Moore, Thomas J. Peters, David R. Ferguson, and Neil F. Stewart

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
Emerging macro-molecular simulations, such as supercoiling of DNA and protein unfolding, have an opportunity to profit from two decades of experience with geometric models within computer-aided geometric design (CAGD). For CAGD, static models are often sufficient, while form and function are inextricably related in biochemistry, resulting in greater attention to critical topological characteristics of these dynamic models. The greater emphasis upon dynamic change in macro-molecular simulations imposes increased demands for faithful integration of topology and geometry, as well as much stricter requirements for computational efficiency. This article presents transitions from the CAGD domain to meet the greater fidelity and performance demands for macro-molecular simulations.
Cite as

Edward L. F. Moore, Thomas J. Peters, David R. Ferguson, and Neil F. Stewart. Integrating Topology and Geometry for Macro-Molecular Simulations. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{moore_et_al:DagSemProc.04351.16,
  author =	{Moore, Edward L. F. and Peters, Thomas J. and Ferguson, David R. and Stewart, Neil F.},
  title =	{{Integrating Topology and Geometry for Macro-Molecular Simulations}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.16},
  URN =		{urn:nbn:de:0030-drops-1240},
  doi =		{10.4230/DagSemProc.04351.16},
  annote =	{Keywords: Computational topology , spline , approximation}
}
  • Refine by Author
  • 4 Peters, Jörg
  • 3 Hahmann, Stefanie
  • 3 Wang, Wenping
  • 2 Farin, Gerald
  • 2 Grandine, Thomas A.
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Computer graphics
  • 1 Computing methodologies → Computer vision
  • 1 Computing methodologies → Modeling and simulation
  • 1 Computing methodologies → Multi-agent systems
  • 1 Computing methodologies → Real-time simulation
  • Show More...

  • Refine by Keyword
  • 3 Geometry
  • 2 computer graphics
  • 2 engineering
  • 2 volumetric modeling
  • 1 B-splines
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2008
  • 2 2023
  • 1 2005
  • 1 2006
  • 1 2011
  • 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact