DROPS

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.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/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.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}
}

Search Results

Documents authored by Goebel, Randy

A 21/16-Approximation for the Minimum 3-Path Partition Problem

Abstract

Cite as

Iterated Belief Change and the Levi Identity

Abstract

Cite as

Thanks for your feedback!

Could not send message