8 Search Results for "Levi, Isaac"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.93
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity

Authors: Jingyang Zhao and Mingyu Xiao

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider k-CVRP in general metrics and on general graphs, where k is the vehicle capacity. All three versions are APX-hard for any fixed k ≥ 3. Assume that the approximation ratio of metric TSP is 3/2. We present a (5/2 - Θ(√{1/k}))-approximation algorithm for the splittable and unit-demand cases, and a (5/2 + ln 2 - Θ(√{1/k}))-approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when k is less than a sufficiently large value, approximately 1.7 x 10⁷. For small values of k, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from 1.792 to 1.500 for k = 3, and from 1.750 to 1.500 for k = 4. For the unsplittable case, we improve the approximation ratio from 1.792 to 1.500 for k = 3, from 2.051 to 1.750 for k = 4, and from 2.249 to 2.157 for k = 5. The approximation ratio for k = 3 surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP - an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.
Cite as

Jingyang Zhao and Mingyu Xiao. Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhao_et_al:LIPIcs.MFCS.2025.93,
  author =	{Zhao, Jingyang and Xiao, Mingyu},
  title =	{{Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{93:1--93:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-242008},
  doi =		{10.4230/LIPIcs.MFCS.2025.93},
  annote =	{Keywords: Combinatorial Optimization, Capacitated Vehicle Routing, Approximation Algorithms, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.22
Learning to Bound for Maximum Common Subgraph Algorithms

Authors: Buddhi W. Kothalawala, Henning Koehler, and Qing Wang

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Identifying the maximum common subgraph between two graphs is a computationally challenging NP-hard problem. While the McSplit algorithm represents a state-of-the-art approach within a branch-and-bound (BnB) framework, several extensions have been proposed to enhance its vertex pair selection strategy, often utilizing reinforcement learning techniques. Nonetheless, the quality of the upper bound remains a critical factor in accelerating the search process by effectively pruning unpromising branches. This research introduces a novel, more restrictive upper bound derived from a detailed analysis of the McSplit algorithm’s generated partitions. To enhance the effectiveness of this bound, we propose a reinforcement learning approach that strategically directs computational effort towards the most promising regions within the search space.
Cite as

Buddhi W. Kothalawala, Henning Koehler, and Qing Wang. Learning to Bound for Maximum Common Subgraph Algorithms. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kothalawala_et_al:LIPIcs.CP.2025.22,
  author =	{Kothalawala, Buddhi W. and Koehler, Henning and Wang, Qing},
  title =	{{Learning to Bound for Maximum Common Subgraph Algorithms}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.22},
  URN =		{urn:nbn:de:0030-drops-238837},
  doi =		{10.4230/LIPIcs.CP.2025.22},
  annote =	{Keywords: Combinatorial Search, Branch and Bound, Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.74
Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay

Authors: Noam Touitou

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We consider the online service with delay problem, in which a server traverses a metric space to serve requests that arrive over time. Requests gather individual delay cost while awaiting service, penalizing service latency; an algorithm seeks to minimize both its movement cost and the total delay cost. Algorithms for the problem (on general metric spaces) are only known for the clairvoyant model, where the algorithm knows future delay cost in advance (e.g., Azar et al., STOC'17; Azar and Touitou, FOCS'19; Touitou, STOC'23). However, in the non-clairvoyant setting, only negative results are known: where n is the size of the metric space and m is the number of requests, there are lower bounds of Ω(√n) and Ω(√m) on competitiveness (Azar et al., STOC'17), that hold even for randomized algorithms (Le et al., SODA'23). In this paper, we present the first algorithm for non-clairvoyant online service with delay. Our algorithm is deterministic and O(min{√n log n, √m log m})-competitive; combined with the lower bounds of Azar et al., this settles the correct competitive ratio for the problem up to logarithmic factors, in terms of both n and m.
Cite as

Noam Touitou. Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 74:1-74:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{touitou:LIPIcs.STACS.2025.74,
  author =	{Touitou, Noam},
  title =	{{Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{74:1--74:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.74},
  URN =		{urn:nbn:de:0030-drops-228995},
  doi =		{10.4230/LIPIcs.STACS.2025.74},
  annote =	{Keywords: Online, Delay, Deadlines, k-server, Non-clairvoyant}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.59
Online Matching with Delays and Size-Based Costs

Authors: Yasushi Kawase and Tomohiro Nakayoshi

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this paper, we introduce the problem of Online Matching with Delays and Size-based Costs (OMDSC). The OMDSC problem involves m requests arriving online. At any time, a group can be formed by matching any number of requests that have been received but remain unmatched. The cost associated with each group is determined by the waiting time for each request within the group and size-dependent cost. The size-dependent cost is specified by a penalty function. Our goal is to partition all the incoming requests into multiple groups while minimizing the total associated cost. This problem is an extension of the TCP acknowledgment problem proposed by Dooly et al. (J. ACM, 2001). It generalizes the cost model for sending acknowledgments. This study reveals the competitive ratios for a fundamental case, in which the penalty function takes only values of either 0 or 1. We classify such penalty functions into three distinct cases: (i) a fixed penalty of 1 regardless of the group size, (ii) a penalty of 0 if and only if the group size is a multiple of a specific integer k, and (iii) other situations. The problem in case (i) is equivalent to the TCP acknowledgment problem, for which Dooly et al. proposed a 2-competitive algorithm. For case (ii), we first show that natural algorithms that match all remaining requests are Ω(√k)-competitive. We then propose an O(log k / log log k)-competitive deterministic algorithm by carefully managing the match size and timing, and prove its optimality. For any penalty function in case (iii), we demonstrate the non-existence of a competitive online algorithm. Additionally, we discuss competitive ratios for other typical penalty functions that are not restricted to take values of 0 or 1.
Cite as

Yasushi Kawase and Tomohiro Nakayoshi. Online Matching with Delays and Size-Based Costs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.STACS.2025.59,
  author =	{Kawase, Yasushi and Nakayoshi, Tomohiro},
  title =	{{Online Matching with Delays and Size-Based Costs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.59},
  URN =		{urn:nbn:de:0030-drops-228846},
  doi =		{10.4230/LIPIcs.STACS.2025.59},
  annote =	{Keywords: Online matching, competitive analysis, delayed service}
}
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.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.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.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.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 Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2023
  • 1 2007
  • 2 2005

  • Refine by Author
  • 3 Levi, Isaac
  • 1 Bonanno, Giacomo
  • 1 Delgrande, James
  • 1 Dubois, Didier
  • 1 Kao, Mong-Jen
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 3 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Online algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Branch-and-bound
  • 1 Theory of computation → Facility location and clustering
  • Show More...

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Belief revision
  • 1 Branch and Bound
  • 1 Capacitated Vehicle Routing
  • 1 Capacitated facility location
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact