4 Search Results for "Smith, William"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.17
Online Matching with Set and Concave Delays

Authors: Lindsey Deryckere and Seeun William Umboh

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

Abstract
We initiate the study of online problems with set delay, where the delay cost at any given time is an arbitrary function of the set of pending requests. In particular, we study the online min-cost perfect matching with set delay (MPMD-Set) problem, which generalises the online min-cost perfect matching with delay (MPMD) problem introduced by Emek et al. (STOC 2016). In MPMD, m requests arrive over time in a metric space of n points. When a request arrives the algorithm must choose to either match or delay the request. The goal is to create a perfect matching of all requests while minimising the sum of distances between matched requests, and the total delay costs incurred by each of the requests. In contrast to previous work we study MPMD-Set in the non-clairvoyant setting, where the algorithm does not know the future delay costs. We first show no algorithm is competitive in n or m. We then study the natural special case of size-based delay where the delay is a non-decreasing function of the number of unmatched requests. Our main result is the first non-clairvoyant algorithms for online min-cost perfect matching with size-based delay that are competitive in terms of m. In fact, these are the first non-clairvoyant algorithms for any variant of MPMD. A key technical ingredient is an analog of the symmetric difference of matchings that may be useful for other special classes of set delay. Furthermore, we prove a lower bound of Ω(n) for any deterministic algorithm and Ω(log n) for any randomised algorithm. These lower bounds also hold for clairvoyant algorithms. Finally, we also give an m-competitive deterministic algorithm for uniform concave delays in the clairvoyant setting.
Cite as

Lindsey Deryckere and Seeun William Umboh. Online Matching with Set and Concave Delays. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deryckere_et_al:LIPIcs.APPROX/RANDOM.2023.17,
  author =	{Deryckere, Lindsey and Umboh, Seeun William},
  title =	{{Online Matching with Set and Concave Delays}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{17:1--17:17},
  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.17},
  URN =		{urn:nbn:de:0030-drops-188423},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.17},
  annote =	{Keywords: online algorithms, matching, delay, non-clairvoyant}
}
Document
DOI: 10.4230/DagRep.12.3.97
3D Morphable Models and Beyond (Dagstuhl Seminar 22121)

Authors: James Gardner, Bernhard Egger, William Smith, Christian Theobalt, and Stefanie Wuhrer

Published in: Dagstuhl Reports, Volume 12, Issue 3 (2022)

Abstract
3D Morphable Models are models separating shape from appearance variation. Typically, they are used as a statistical prior in computer graphics and vision. Recent success with neural representations have caused a resurgence of interest in visual computing problems, leading to more accurate, higher fidelity, more expressive, and memory-efficient solutions. This report documents the program and the outcomes of Dagstuhl Seminar 22121, "3D Morphable Models and Beyond". This meeting of 39 researchers covered various topics, including 3D morphable models, implicit neural representations, physics-inspired approaches, and more. We summarise the discussions, presentations and results of this workshop.
Cite as

James Gardner, Bernhard Egger, William Smith, Christian Theobalt, and Stefanie Wuhrer. 3D Morphable Models and Beyond (Dagstuhl Seminar 22121). In Dagstuhl Reports, Volume 12, Issue 3, pp. 97-116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{gardner_et_al:DagRep.12.3.97,
  author =	{Gardner, James and Egger, Bernhard and Smith, William and Theobalt, Christian and Wuhrer, Stefanie},
  title =	{{3D Morphable Models and Beyond (Dagstuhl Seminar 22121)}},
  pages =	{97--116},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{3},
  editor =	{Gardner, James and Egger, Bernhard and Smith, William and Theobalt, Christian and Wuhrer, Stefanie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.3.97},
  URN =		{urn:nbn:de:0030-drops-172701},
  doi =		{10.4230/DagRep.12.3.97},
  annote =	{Keywords: 3D Computer Vision, Generative Models, Neural Rendering, Implicit Representations, Computer Graphics, Statistical Modelling}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.27
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

Authors: Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C₀ of G, how can we compute a second Hamiltonian cycle C₁ ≠ C₀ of G? Cedric Smith and William Tutte proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is a deterministic algorithm which computes the second Hamiltonian cycle in O(n⋅2^0.299862744n) = O(1.23103ⁿ) time and in linear space, thus improving the state of the art running time of O*(2^0.3n) = O(1.2312ⁿ) for solving this problem (among deterministic algorithms running in polynomial space). Whenever the input graph G does not contain any induced cycle C₆ on 6 vertices, the running time becomes O(n⋅ 2^0.2971925n) = O(1.22876ⁿ). Our algorithm is based on a fundamental structural property of Thomason’s lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a (not necessarily cubic) Hamiltonian graph G with a given Hamiltonian cycle C₀ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least n - 4α (√n+2α)+8, where α = (Δ-2)/(δ-2) and δ,Δ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.
Cite as

Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.MFCS.2020.27,
  author =	{Deligkas, Argyrios and Mertzios, George B. and Spirakis, Paul G. and Zamaraev, Viktor},
  title =	{{Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.27},
  URN =		{urn:nbn:de:0030-drops-126953},
  doi =		{10.4230/LIPIcs.MFCS.2020.27},
  annote =	{Keywords: Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm}
}
Document
DOI: 10.4230/DagRep.9.3.16
3D Morphable Models (Dagstuhl Seminar 19102)

Authors: Bernhard Egger, William Smith, Christian Theobalt, and Thomas Vetter

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract
3D Morphable Models is a statistical object model separating shape from appearance variation. Typically, they are used as a statistical prior in computer graphics and vision. This report summarizes the Dagstuhl seminar on 3D Morphable Models, March 3-8, 2019. It was a first specific meeting of a broader group of people working with 3D Morphable Models of faces and bodies. This meeting of 26 researchers was held 20 years after the seminal work was published at Siggraph. We summarize the discussions, presentations and results of this workshop.
Cite as

Bernhard Egger, William Smith, Christian Theobalt, and Thomas Vetter. 3D Morphable Models (Dagstuhl Seminar 19102). In Dagstuhl Reports, Volume 9, Issue 3, pp. 16-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{egger_et_al:DagRep.9.3.16,
  author =	{Egger, Bernhard and Smith, William and Theobalt, Christian and Vetter, Thomas},
  title =	{{3D Morphable Models (Dagstuhl Seminar 19102)}},
  pages =	{16--38},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{Egger, Bernhard and Smith, William and Theobalt, Christian and Vetter, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.3.16},
  URN =		{urn:nbn:de:0030-drops-112894},
  doi =		{10.4230/DagRep.9.3.16},
  annote =	{Keywords: 3D Computer Vision, Analysis-by-Synthesis, Computer Graphics, Generative Models, Statistical Modelling}
}
  • Refine by Author
  • 2 Egger, Bernhard
  • 2 Smith, William
  • 2 Theobalt, Christian
  • 1 Deligkas, Argyrios
  • 1 Deryckere, Lindsey
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → 3D imaging
  • 1 Computing methodologies → Animation
  • 1 Computing methodologies → Computer graphics
  • 1 Computing methodologies → Computer vision
  • 1 Computing methodologies → Image-based rendering
  • Show More...

  • Refine by Keyword
  • 2 3D Computer Vision
  • 2 Computer Graphics
  • 2 Generative Models
  • 2 Statistical Modelling
  • 1 Analysis-by-Synthesis
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020
  • 1 2022
  • 1 2023

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