74 Search Results for "Wirth, Anthony"

Volume

LIPIcs, Volume 322

35th International Symposium on Algorithms and Computation (ISAAC 2024)

ISAAC 2024, December 8-11, 2024, Sydney, Australia

Editors: Julián Mestre and Anthony Wirth

Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2024
LIPIcs, Volume 322, ISAAC 2024, Complete Volume

Authors: Julián Mestre and Anthony Wirth

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
LIPIcs, Volume 322, ISAAC 2024, Complete Volume
Cite as

35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 1-956, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{mestre_et_al:LIPIcs.ISAAC.2024,
  title =	{{LIPIcs, Volume 322, ISAAC 2024, Complete Volume}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{1--956},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024},
  URN =		{urn:nbn:de:0030-drops-222718},
  doi =		{10.4230/LIPIcs.ISAAC.2024},
  annote =	{Keywords: LIPIcs, Volume 322, ISAAC 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Julián Mestre and Anthony Wirth

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mestre_et_al:LIPIcs.ISAAC.2024.0,
  author =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.0},
  URN =		{urn:nbn:de:0030-drops-222702},
  doi =		{10.4230/LIPIcs.ISAAC.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2024.1
Algorithmic Problems in Discrete Choice (Invited Talk)

Authors: Ravi Kumar

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In discrete choice, a user selects one option from a finite set of available alternatives, a process that is crucial for recommendation systems applications in e-commerce, social media, search engines, etc. A popular way to model discrete choice is through Random Utility Models (RUMs). RUMs assume that users assign values to options and choose the one with the highest value from among the available alternatives. RUMs have become increasingly important in the Web era; they offer an elegant mathematical framework for researchers to model user choices and predict user behavior based on (possibly limited) observations. While RUMs have been extensively studied in behavioral economics and social sciences, many basic algorithmic tasks remain poorly understood. In this talk, we will discuss various algorithmic and learning questions concerning RUMs.
Cite as

Ravi Kumar. Algorithmic Problems in Discrete Choice (Invited Talk). In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kumar:LIPIcs.ISAAC.2024.1,
  author =	{Kumar, Ravi},
  title =	{{Algorithmic Problems in Discrete Choice}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.1},
  URN =		{urn:nbn:de:0030-drops-221287},
  doi =		{10.4230/LIPIcs.ISAAC.2024.1},
  annote =	{Keywords: discrete choice theory, random utility models, user behavior}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2024.2
Data Privacy: The Land Where Average Cases Don't Exist and Assumptions Quickly Perish (Invited Talk)

Authors: Olga Ohrimenko

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Machine learning on personal and sensitive data raises serious privacy concerns and creates potential for inadvertent information leakage (e.g., extraction of private messages or images from generative models). However, incorporating analysis of such data in decision making can benefit individuals and society at large (e.g., in healthcare). To strike a balance between these two conflicting objectives, one must ensure that data analysis with strong confidentiality guarantees is deployed and securely implemented. Differential privacy (DP) is emerging as a leading framework for analyzing data while maintaining mathematical privacy guarantees. Although it has seen some real-world deployment (e.g., by Apple, Microsoft, and Google), such instances remain limited and are often constrained to specific scenarios. Why? In this talk, I argue that part of the challenge lies in the assumptions DP makes about its deployment environment. By examining several DP systems and their assumptions, I demonstrate how private information can be extracted using, for example, side-channel information or the ability to rewind system’s state. I then give an overview of efficient algorithms and protocols to realize these assumptions and ensure secure deployment of differential privacy.
Cite as

Olga Ohrimenko. Data Privacy: The Land Where Average Cases Don't Exist and Assumptions Quickly Perish (Invited Talk). In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ohrimenko:LIPIcs.ISAAC.2024.2,
  author =	{Ohrimenko, Olga},
  title =	{{Data Privacy: The Land Where Average Cases Don't Exist and Assumptions Quickly Perish}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.2},
  URN =		{urn:nbn:de:0030-drops-221290},
  doi =		{10.4230/LIPIcs.ISAAC.2024.2},
  annote =	{Keywords: Differential privacy, side-channel attacks, trusted execution environment, privacy budget, state continuity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2024.3
Role of Structured Matrices in Fine-Grained Algorithm Design (Invited Talk)

Authors: Barna Saha

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Fine-grained complexity attempts to precisely determine the time complexity of a problem and has emerged as a guide for algorithm design in recent times. Some of the central problems in fine-grain complexity deals with computation of distances. For example, computing all pairs shortest paths in a weighted graph, computing edit distance between two sequences or two trees, and computing distance of a sequence from a context free language. Many of these problems reduce to computation of matrix products over various algebraic structures, predominantly over the (min,+) semiring. Obtaining a truly subcubic algorithm for (min,+) product is one of the outstanding open questions in computer science. Interestingly many of the aforementioned distance computation problems have some additional structural properties. Specifically, when we perturb the inputs slightly, we do not expect a huge change in the output. This simple yet powerful observation has led to better algorithms for many problems for which we were able to improve the running time after several decades. This includes problems such as the Language Edit Distance, RNA folding, and Dyck Edit Distance. Indeed, this structure in the problem leads to matrices that have the Lipschitz property, and we gave the first truly subcubic time algorithm for computing (min,+) product over such Lipschitz matrices. Follow-up work by several researchers obtained improved bounds for monotone matrices, and for (min,+) convolution under similar structures leading to improved bounds for a series of optimization problems. These result in not just faster algorithms for exact computation but also for approximation algorithms. In particular, we show how fast (min,+) product computation over monotone matrices can lead to better additive approximation algorithms for computing all pairs shortest paths on unweighted undirected graphs, leading to improvements after twenty four years.
Cite as

Barna Saha. Role of Structured Matrices in Fine-Grained Algorithm Design (Invited Talk). In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{saha:LIPIcs.ISAAC.2024.3,
  author =	{Saha, Barna},
  title =	{{Role of Structured Matrices in Fine-Grained Algorithm Design}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.3},
  URN =		{urn:nbn:de:0030-drops-221303},
  doi =		{10.4230/LIPIcs.ISAAC.2024.3},
  annote =	{Keywords: Fine-Grained Complexity, Fast Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.4
Minimum Plane Bichromatic Spanning Trees

Authors: Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case.
Cite as

Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth. Minimum Plane Bichromatic Spanning Trees. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ISAAC.2024.4,
  author =	{A. Akitaya, Hugo and Biniaz, Ahmad and Demaine, Erik D. and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D.},
  title =	{{Minimum Plane Bichromatic Spanning Trees}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.4},
  URN =		{urn:nbn:de:0030-drops-221319},
  doi =		{10.4230/LIPIcs.ISAAC.2024.4},
  annote =	{Keywords: Bichromatic Spanning Tree, Minimum Spanning Tree, Plane Tree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.5
Constrained Two-Line Center Problems

Authors: Taehoon Ahn and Sang Won Bae

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Given a set P of n points in the plane, the two-line center problem asks to find two lines that minimize the maximum distance from each point in P to its closer one of the two resulting lines. The currently best algorithm for the problem takes O(n² log² n) time by Jaromczyk and Kowaluk in 1995. In this paper, we present faster algorithms for three variants of the two-line center problem in which the orientations of the resulting lines are constrained. Specifically, our algorithms solve the problem in O(n log n) time when the orientations of both lines are fixed; in O(n log³ n) time when the orientation of one line is fixed; and in O(n² α(n) log n) time when the angle between the two lines is fixed, where α(n) denotes the inverse Ackermann function.
Cite as

Taehoon Ahn and Sang Won Bae. Constrained Two-Line Center Problems. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2024.5,
  author =	{Ahn, Taehoon and Bae, Sang Won},
  title =	{{Constrained Two-Line Center Problems}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.5},
  URN =		{urn:nbn:de:0030-drops-221327},
  doi =		{10.4230/LIPIcs.ISAAC.2024.5},
  annote =	{Keywords: two-line center problem, geometric location problem, geometric optimization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.6
Dynamic Parameterized Problems on Unit Disk Graphs

Authors: Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, and Chanho Song

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In this paper, we study fundamental parameterized problems such as k-Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk graphs. Given a vertex set V changing dynamically under vertex insertions and deletions, our goal is to maintain data structures so that the aforementioned parameterized problems on the unit disk graph induced by V can be solved efficiently. Although dynamic parameterized problems on general graphs have been studied extensively, no previous work focuses on unit disk graphs. In this paper, we present the first data structures for fundamental parameterized problems on dynamic unit disk graphs. More specifically, our data structure supports 2^O(√k) update time and O(k) query time for k-Path/Cycle. For the other problems, our data structures support O(log n) update time and 2^O(√k) query time, where k denotes the output size.
Cite as

Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, and Chanho Song. Dynamic Parameterized Problems on Unit Disk Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ISAAC.2024.6,
  author =	{An, Shinwoo and Cho, Kyungjin and Jang, Leo and Jung, Byeonghyeon and Lee, Yudam and Oh, Eunjin and Shin, Donghun and Shin, Hyeonjun and Song, Chanho},
  title =	{{Dynamic Parameterized Problems on Unit Disk Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.6},
  URN =		{urn:nbn:de:0030-drops-221337},
  doi =		{10.4230/LIPIcs.ISAAC.2024.6},
  annote =	{Keywords: Unit disk graphs, dynamic parameterized algorithms, kernelization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.7
On the Connected Minimum Sum of Radii Problem

Authors: Hyung-Chan An and Mong-Jen Kao

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In this paper, we consider the study for the connected minimum sum of radii problem. In this problem, we are given as input a metric defined on a set of facilities and clients, along with some cost parameters. The objective is to open a subset of facilities, assign every client to an open facilitiy, and connect open facilities using a Steiner tree so that the weighted (by cost parameters) sum of the maximum assignment distance of each facility and the Steiner tree cost is minimized. This problem introduces the min-sum radii objective, an objective function that is widely considered in the clustering literature, to the connected facility location problem, a well-studied network design/clustering problem. This problem is useful in communication network design on a shared medium, or energy optimization of mobile wireless chargers. We present both a constant-factor approximation algorithm and hardness results for this problem. Our algorithm is based on rounding an LP relaxation that jointly models the min-sum of radii problem and the rooted Steiner tree problem. To round the solution we use a careful clustering procedure that guarantees that every open facility has a proxy client nearby. This allows a reinterpretation for part of the LP solution as a fractional rooted Steiner tree. Combined with a cost filtering technique, this yields a 5.542-approximation algorithm.
Cite as

Hyung-Chan An and Mong-Jen Kao. On the Connected Minimum Sum of Radii Problem. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ISAAC.2024.7,
  author =	{An, Hyung-Chan and Kao, Mong-Jen},
  title =	{{On the Connected Minimum Sum of Radii Problem}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.7},
  URN =		{urn:nbn:de:0030-drops-221342},
  doi =		{10.4230/LIPIcs.ISAAC.2024.7},
  annote =	{Keywords: connected minimum sum of radii, minimum sum of radii, connected facility location, approximation algorithms, Steiner trees}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.8
Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths

Authors: Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, and Marek Chrobak

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We consider the classical single-source shortest path problem in directed weighted graphs. D. Eppstein proved recently an Ω(n³) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this Ω(n³) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm.
Cite as

Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, and Marek Chrobak. Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{atalig_et_al:LIPIcs.ISAAC.2024.8,
  author =	{Atalig, Sunny and Hickerson, Alexander and Srivastav, Arrdya and Zheng, Tingting and Chrobak, Marek},
  title =	{{Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.8},
  URN =		{urn:nbn:de:0030-drops-221356},
  doi =		{10.4230/LIPIcs.ISAAC.2024.8},
  annote =	{Keywords: single-source shortest paths, lower bounds, decision trees}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.9
Fault-Tolerant Bounded Flow Preservers

Authors: Shivam Bansal, Keerti Choudhary, Harkirat Dhanoa, and Harsh Wardhan

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Given a directed graph G = (V, E) with n vertices, m edges and a designated source vertex s ∈ V, we consider the question of finding a sparse subgraph H of G that preserves the flow from s up to a given threshold λ even after failure of k edges. We refer to such subgraphs as (λ,k)-fault-tolerant bounded-flow-preserver ((λ,k)-FT-BFP). Formally, for any F ⊆ E of at most k edges and any v ∈ V, the (s, v)-max-flow in H⧵F is equal to (s, v)-max-flow in G⧵F, if the latter is bounded by λ, and at least λ otherwise. Our contributions are summarized as follows: 1) We provide a polynomial time algorithm that given any graph G constructs a (λ,k)-FT-BFP of G with at most λ 2^kn edges. 2) We also prove a matching lower bound of Ω(λ 2^kn) on the size of (λ,k)-FT-BFP. In particular, we show that for every λ,k,n ⩾ 1, there exists an n-vertex directed graph whose optimal (λ,k)-FT-BFP contains Ω(min{2^kλ n, n²}) edges. 3) Furthermore, we show that the problem of computing approximate (λ,k)-FT-BFP is NP-hard for any approximation ratio that is better than O(log(λ^{-1} n)).
Cite as

Shivam Bansal, Keerti Choudhary, Harkirat Dhanoa, and Harsh Wardhan. Fault-Tolerant Bounded Flow Preservers. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.ISAAC.2024.9,
  author =	{Bansal, Shivam and Choudhary, Keerti and Dhanoa, Harkirat and Wardhan, Harsh},
  title =	{{Fault-Tolerant Bounded Flow Preservers}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.9},
  URN =		{urn:nbn:de:0030-drops-221363},
  doi =		{10.4230/LIPIcs.ISAAC.2024.9},
  annote =	{Keywords: Fault-tolerant Data-structures, Max-flow, Bounded Flow Preservers}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.10
Optimal Sensitivity Oracle for Steiner Mincut

Authors: Koustav Bhanja

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Let G = (V,E) be an undirected weighted graph on n = |V| vertices and S ⊆ V be a Steiner set. Steiner mincut is a well-studied concept, which also provides a generalization to both (s,t)-mincut (when |S| = 2) and global mincut (when |S| = n). Here, we address the problem of designing a compact data structure that can efficiently report a Steiner mincut and its capacity after the failure of any edge in G; such a data structure is known as a Sensitivity Oracle for Steiner mincut. In the area of minimum cuts, although many Sensitivity Oracles have been designed in unweighted graphs, however, in weighted graphs, Sensitivity Oracles exist only for (s,t)-mincut [Annals of Operations Research 1991, NETWORKS 2019, ICALP 2024], which is just a special case of Steiner mincut. Here, we generalize this result from |S| = 2 to any arbitrary set S ⊆ V, that is, 2 ≤ |S| ≤ n. We first design an {O}(n²) space Sensitivity Oracle for Steiner mincut by suitably generalizing the approach used for (s,t)-mincuts [Annals of Operations Research 1991, NETWORKS 2019]. However, the main question that arises quite naturally is the following. Can we design a Sensitivity Oracle for Steiner mincut that breaks the {O}(n²) bound on space? In this article, we present the following two results that provide an answer to this question. 1. Sensitivity Oracle: Assuming the capacity of every edge is known, a) there is an O(n) space data structure that can report the capacity of Steiner mincut in O(1) time and b) there is an O(n(n-|S|+1)) space data structure that can report a Steiner mincut in O(n) time after the failure of any edge in G. 2. Lower Bound: We show that any data structure that, after the failure of any edge in G, can report a Steiner mincut or its capacity must occupy Ω(n²) bits of space in the worst case, irrespective of the size of the Steiner set. The lower bound in (2) shows that the assumption in (1) is essential to break the Ω(n²) lower bound on space. Sensitivity Oracle in (1.b) occupies only subquadratic, that is O(n^{1+ε}), space if |S| = n-n^ε+1, for every ε ∈ [0,1). For |S| = n-k for any constant k ≥ 0, it occupies only O(n) space. So, we also present the first Sensitivity Oracle occupying O(n) space for global mincut. In addition, we are able to match the existing best-known bounds on both space and query time for (s,t)-mincut [Annals of Operations Research 1991, NETWORKS 2019] in undirected graphs.
Cite as

Koustav Bhanja. Optimal Sensitivity Oracle for Steiner Mincut. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhanja:LIPIcs.ISAAC.2024.10,
  author =	{Bhanja, Koustav},
  title =	{{Optimal Sensitivity Oracle for Steiner Mincut}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.10},
  URN =		{urn:nbn:de:0030-drops-221371},
  doi =		{10.4230/LIPIcs.ISAAC.2024.10},
  annote =	{Keywords: mincut, (s, t)-mincut, Steiner mincut, fault tolerant structures, data structure, vital edges, vitality, sensitivity oracle}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.11
Temporal Queries for Dynamic Temporal Forests

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Alessandro Straziota

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In a temporal forest each edge has an associated set of time labels that specify the time instants in which the edges are available. A temporal path from vertex u to vertex v in the forest is a selection of a label for each edge in the unique path from u to v, assuming it exists, such that the labels selected for any two consecutive edges are non-decreasing. We design linear-size data structures that maintain a temporal forest of rooted trees under addition and deletion of both edge labels and singleton vertices, insertion of root-to-node edges, and removal of edges with no labels. Such data structures can answer temporal reachability, earliest arrival, and latest departure queries. All queries and updates are handled in polylogarithmic worst-case time. Our results can be adapted to deal with latencies. More precisely, all the worst-case time bounds are asymptotically unaffected when latencies are uniform. For arbitrary latencies, the update time becomes amortized in the incremental case where only label additions and edge/singleton insertions are allowed as well as in the decremental case in which only label deletions and edge/singleton removals are allowed. To the best of our knowledge, the only previously known data structure supporting temporal reachability queries is due to Brito, Albertini, Casteigts, and Travençolo [Social Network Analysis and Mining, 2021], which can handle general temporal graphs, answers queries in logarithmic time in the worst case, but requires an amortized update time that is quadratic in the number of vertices, up to polylogarithmic factors.
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Alessandro Straziota. Temporal Queries for Dynamic Temporal Forests. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ISAAC.2024.11,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Straziota, Alessandro},
  title =	{{Temporal Queries for Dynamic Temporal Forests}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.11},
  URN =		{urn:nbn:de:0030-drops-221382},
  doi =		{10.4230/LIPIcs.ISAAC.2024.11},
  annote =	{Keywords: temporal graphs, temporal reachability, earliest arrival, latest departure, dynamic forests}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.12
Partitioning Problems with Splittings and Interval Targets

Authors: Samuel Bismuth, Vladislav Makarov, Erel Segal-Halevi, and Dana Shapira

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
The n-way number partitioning problem is a classic problem in combinatorial optimization, with applications to diverse settings such as fair allocation and machine scheduling. All these problems are NP-hard, but various approximation algorithms are known. We consider three closely related kinds of approximations. The first two variants optimize the partition such that: in the first variant some fixed number s of items can be split between two or more bins and in the second variant we allow at most a fixed number t of splittings. The third variant is a decision problem: the largest bin sum must be within a pre-specified interval, parameterized by a fixed rational number u times the largest item size. When the number of bins n is unbounded, we show that every variant is strongly NP-complete. When the number of bins n is fixed, the running time depends on the fixed parameters s,t,u. For each variant, we give a complete picture of its running time. For n = 2, the running time is easy to identify. Our main results consider any fixed integer n ≥ 3. Using a two-way polynomial-time reduction between the first and the third variant, we show that n-way number-partitioning with s split items can be solved in polynomial time if s ≥ n-2, and it is NP-complete otherwise. Also, n-way number-partitioning with t splittings can be solved in polynomial time if t ≥ n-1, and it is NP-complete otherwise. Finally, we show that the third variant can be solved in polynomial time if u ≥ (n-2)/n, and it is NP-complete otherwise. Our positive results for the optimization problems consider both min-max and max-min versions. Using the same reduction, we provide a fully polynomial-time approximation scheme for the case where the number of split items is lower than n-2.
Cite as

Samuel Bismuth, Vladislav Makarov, Erel Segal-Halevi, and Dana Shapira. Partitioning Problems with Splittings and Interval Targets. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bismuth_et_al:LIPIcs.ISAAC.2024.12,
  author =	{Bismuth, Samuel and Makarov, Vladislav and Segal-Halevi, Erel and Shapira, Dana},
  title =	{{Partitioning Problems with Splittings and Interval Targets}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.12},
  URN =		{urn:nbn:de:0030-drops-221394},
  doi =		{10.4230/LIPIcs.ISAAC.2024.12},
  annote =	{Keywords: Number Partitioning, Fair Division, Identical Machine Scheduling}
}
  • Refine by Author
  • 14 Wirth, Anthony
  • 4 Gan, Junhao
  • 3 Mestre, Julián
  • 3 Staals, Frank
  • 2 Bose, Prosenjit
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 Approximation Algorithms
  • 3 approximation algorithms
  • 3 parameterized complexity
  • 2 Algorithms
  • 2 Fault-tolerant search
  • Show More...

  • Refine by Type
  • 73 document
  • 1 volume

  • Refine by Publication Year
  • 65 2024
  • 2 2020
  • 2 2023
  • 1 2016
  • 1 2017
  • Show More...

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 About DROPS Imprint Privacy Contact