4 Search Results for "Levi, Isaac"

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.45
Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost

Authors: Mong-Jen Kao

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We consider the hard-capacitated facility location problem with uniform facility cost (CFL-UFC). This problem arises as an indicator variation between the general CFL problem and the uncapacitated facility location (UFL) problem, and is related to the profound capacitated k-median problem (CKM). In this work, we present a rounding-based 4-approximation algorithm for this problem, built on a two-staged rounding scheme that incorporates a set of novel ideas and also techniques developed in the past for both facility location and capacitated covering problems. Our result improves the decades-old LP-based ratio of 5 for this problem due to Levi et al. since 2004. We believe that the techniques developed in this work are of independent interests and may further lead to insights and implications for related problems.
Cite as

Mong-Jen Kao. Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kao:LIPIcs.ISAAC.2023.45,
  author =	{Kao, Mong-Jen},
  title =	{{Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.45},
  URN =		{urn:nbn:de:0030-drops-193474},
  doi =		{10.4230/LIPIcs.ISAAC.2023.45},
  annote =	{Keywords: Capacitated facility location, Hard capacities, Uniform facility cost}
}
Document
DOI: 10.4230/DagSemProc.07351.17
Probability Logic and Logical Probability

Authors: Isaac Levi

Published in: Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007)

Abstract
Authors like Keynes, H. Jeffreys and Carnap advocated using a concept of "logical probability". Logical probability had the following properties: (a) it was representable as a function from potential states of full belief (or "evidence") to states of subjective or credal probability judgment. (b) Such functions were alleged to be constrained by principles of probability logic. (c) All rational agents were supposed to be obliged to adopt the standard function that probability logic prescribed. In this essay, it is argued that these three requirements could be satisfied only if probability logic prescribed that credal probability should be numerically determinate. Keynes denied that it should numerically determinate and Carnap abandoned the idea that probability logic could supply a determinate function from states of full belief to numerically determinate credal states that all rational agents ought to adopt. The paper explains that once this is conceded, logical probability ought to be interpreted rather differently than it is customarily is.
Cite as

Isaac Levi. Probability Logic and Logical Probability. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{levi:DagSemProc.07351.17,
  author =	{Levi, Isaac},
  title =	{{Probability Logic and Logical Probability}},
  booktitle =	{Formal Models of Belief Change in Rational Agents},
  pages =	{1--27},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7351},
  editor =	{Giacomo Bonanno and James Delgrande and J\'{e}r\^{o}me Lang and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.17},
  URN =		{urn:nbn:de:0030-drops-12105},
  doi =		{10.4230/DagSemProc.07351.17},
  annote =	{Keywords: Probability, full belief, logic, evidence}
}
Document
DOI: 10.4230/DagSemProc.05321.1
05321 – Panel on belief change

Authors: Isaac Levi, Giacomo Bonanno, Bernard Walliser, Didier Dubois, Hans Rott, James Delgrande, and Jérôme Lang

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

Abstract
This document gathers the panelists' contribution.
Cite as

Isaac Levi, Giacomo Bonanno, Bernard Walliser, Didier Dubois, Hans Rott, James Delgrande, and Jérôme Lang. 05321 – Panel on belief change. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{levi_et_al:DagSemProc.05321.1,
  author =	{Levi, Isaac and Bonanno, Giacomo and Walliser, Bernard and Dubois, Didier and Rott, Hans and Delgrande, James and Lang, J\'{e}r\^{o}me},
  title =	{{05321 – Panel on belief change}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--12},
  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.1},
  URN =		{urn:nbn:de:0030-drops-3580},
  doi =		{10.4230/DagSemProc.05321.1},
  annote =	{Keywords: Belief revision, iterated belief revision, update, merging, dynamic logic, possibility theory, conditionals, social choice, distance, complexity}
}
Document
DOI: 10.4230/DagSemProc.05321.10
Degrees of Belief

Authors: Isaac Levi

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

Abstract
A discussion of three kinds of degree of belief: subjective (credal) probability, degree of belief in the maximizing sense (expected epistemic utility) and degree of belief in the satisficing sense (Shackle type degrees of belief). The relations between these concepts and full belief (absolute certainty) and other qualitative assessments of belief (mere belief or plain belief) will be considered.
Cite as

Isaac Levi. Degrees of Belief. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, pp. 1-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{levi:DagSemProc.05321.10,
  author =	{Levi, Isaac},
  title =	{{Degrees of Belief}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  pages =	{1--35},
  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.10},
  URN =		{urn:nbn:de:0030-drops-3271},
  doi =		{10.4230/DagSemProc.05321.10},
  annote =	{Keywords: Inductive expansion, credal probability, maximizing and satisficing, full belief.}
}
  • Refine by Author
  • 3 Levi, Isaac
  • 1 Bonanno, Giacomo
  • 1 Delgrande, James
  • 1 Dubois, Didier
  • 1 Kao, Mong-Jen
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 1 Belief revision
  • 1 Capacitated facility location
  • 1 Hard capacities
  • 1 Inductive expansion
  • 1 Probability
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2005
  • 1 2007
  • 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