3 Search Results for "Goebel, Randy"

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.46
A 21/16-Approximation for the Minimum 3-Path Partition Problem

Authors: Yong Chen, Randy Goebel, Bing Su, Weitian Tong, Yao Xu, and An Zhang

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
The minimum k-path partition (Min-k-PP for short) problem targets to partition an input graph into the smallest number of paths, each of which has order at most k. We focus on the special case when k=3. Existing literature mainly concentrates on the exact algorithms for special graphs, such as trees. Because of the challenge of NP-hardness on general graphs, the approximability of the Min-3-PP problem attracts researchers' attention. The first approximation algorithm dates back about 10 years and achieves an approximation ratio of 3/2, which was recently improved to 13/9 and further to 4/3. We investigate the 3/2-approximation algorithm for the Min-3-PP problem and discover several interesting structural properties. Instead of studying the unweighted Min-3-PP problem directly, we design a novel weight schema for l-paths, l in {1, 2, 3}, and investigate the weighted version. A greedy local search algorithm is proposed to generate a heavy path partition. We show the achieved path partition has the least 1-paths, which is also the key ingredient for the algorithms with ratios 13/9 and 4/3. When switching back to the unweighted objective function, we prove the approximation ratio 21/16 via amortized analysis.
Cite as

Yong Chen, Randy Goebel, Bing Su, Weitian Tong, Yao Xu, and An Zhang. A 21/16-Approximation for the Minimum 3-Path Partition Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2019.46,
  author =	{Chen, Yong and Goebel, Randy and Su, Bing and Tong, Weitian and Xu, Yao and Zhang, An},
  title =	{{A 21/16-Approximation for the Minimum 3-Path Partition Problem}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.46},
  URN =		{urn:nbn:de:0030-drops-115422},
  doi =		{10.4230/LIPIcs.ISAAC.2019.46},
  annote =	{Keywords: 3-path partition, exact set cover, approximation algorithm, local search, amortized analysis}
}
Document
DOI: 10.4230/DagRep.5.2.128
Smart Buildings and Smart Grids (Dagstuhl Seminar 15091)

Authors: Hans-Arno Jacobsen, Randy H. Katz, Hartmut Schmeck, and Christoph Goebel

Published in: Dagstuhl Reports, Volume 5, Issue 2 (2015)

Abstract
This report provides an overview of the program, discussions, and outcomes of Dagstuhl Seminar 15091 "Smart Buildings and Smart Grids", which took place from 22-27 February 2015 at Schloss Dagstuhl - Leibniz Center for Informatics. The main goal of the seminar was to provide a forum for leading Energy Informatics (EI) researchers to discuss their recent research on Smart Buildings and Smart Grids, to further elaborate EI research agenda and methods, and to kick-start new research projects with industry. The report contains abstracts of talks that were held by the participants and the outcomes of several discussion sessions on the focal topics of the seminar (e.g., information technology driven developments in building and power system management, as well as cross-cutting topics, such as computer networks, data management, and system design.
Cite as

Hans-Arno Jacobsen, Randy H. Katz, Hartmut Schmeck, and Christoph Goebel. Smart Buildings and Smart Grids (Dagstuhl Seminar 15091). In Dagstuhl Reports, Volume 5, Issue 2, pp. 128-175, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{jacobsen_et_al:DagRep.5.2.128,
  author =	{Jacobsen, Hans-Arno and Katz, Randy H. and Schmeck, Hartmut and Goebel, Christoph},
  title =	{{Smart Buildings and Smart Grids (Dagstuhl Seminar 15091)}},
  pages =	{128--175},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{2},
  editor =	{Jacobsen, Hans-Arno and Katz, Randy H. and Schmeck, Hartmut and Goebel, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.2.128},
  URN =		{urn:nbn:de:0030-drops-52109},
  doi =		{10.4230/DagRep.5.2.128},
  annote =	{Keywords: Energy Informatics, Smart Grids, Smart Buildings, Cyber-Physical Systems}
}
Document
DOI: 10.4230/DagSemProc.05321.11
Iterated Belief Change and the Levi Identity

Authors: Abhaya Nayak, Randy Goebel, Mehmet Orgun, and Tam Pham

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)

Abstract
Most works on iterated belief change have focussed on iterated belief revision, namely, on how to compute (K star x) star y. However, historically, belief revision has been defined in terms of belief expansion and belief contraction that have been viewed as primary operations. Accordingly, what we should be looking at are constructions like: (K+x)+y, (K-x)+y, (K-x)+y and (K-x)-y. The first two constructions are relatively innocuous. The last two are, however, more problematic. We look at these sequential operations. In the process, we use the Levi Identity as the guiding principle behind state changes (as opposed to belief set changes).
Cite as

Abhaya Nayak, Randy Goebel, Mehmet Orgun, and Tam Pham. Iterated Belief Change and the Levi Identity. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{nayak_et_al:DagSemProc.05321.11,
  author =	{Nayak, Abhaya and Goebel, Randy and Orgun, Mehmet and Pham, Tam},
  title =	{{Iterated Belief Change and the Levi Identity}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.11},
  URN =		{urn:nbn:de:0030-drops-3317},
  doi =		{10.4230/DagSemProc.05321.11},
  annote =	{Keywords: Iterated belief change, iterated belief contraction, Levi Identity}
}
  • Refine by Author
  • 2 Goebel, Randy
  • 1 Chen, Yong
  • 1 Goebel, Christoph
  • 1 Jacobsen, Hans-Arno
  • 1 Katz, Randy H.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 3-path partition
  • 1 Cyber-Physical Systems
  • 1 Energy Informatics
  • 1 Iterated belief change
  • 1 Levi Identity
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2005
  • 1 2015
  • 1 2019

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