1,720,979 research outputs found
New Algorithms for Steiner Tree Reoptimization
Full text linkReoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}\end{document} -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P = NP \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}\end{document
Finding diameter-reducing shortcuts in trees
Full text linkIn the k-Diameter-Optimally Augmenting Tree Problem we are given a tree T of n vertices embedded in an unknown metric space. An oracle can report the cost of any edge in constant time, and we want to augment T with k shortcuts to minimize the resulting diameter. When k = 1, O(n log n)-time algorithms exist for paths and trees. We show that o(n(2)) queries cannot provide a better than 10/9-approximation for trees when k >= 3. For any constant epsilon > 0, we design a linear-time (1 + epsilon)-approximation algorithm for paths when k = o(root logn), thus establishing a dichotomy between paths and trees for k >= 3. Our algorithm employs an ad-hoc data structure, which we also use in a linear-time 4approximation algorithm for trees, and to compute the diameter of (possibly non-metric) graphs with n + k - 1 edges in time O (nk log n). (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
New approximation algorithms for the heterogeneous weighted delivery problem
No full textWe study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n-vertex edge-weighted graph G, have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k=1, and is 4ρ-approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k=O(logn), closing a problem left open in [Bärtschi et al., ATMOS'17]. This algorithm can be turned into an O(k)-approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ̃(log3n)-approximation algorithm for the general case
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Full text linkWe design sensitivity oracles for error-prone networks. For a network problem Π, the data structure preprocesses a network G = (V, E) and sensitivity parameter f such that, for any set F ⊆ V ∪ E of up to f link or node failures, it can report the solution of Π in G−F. We study three network problems Π. • L-HOP SHORTEST PATH: Given s, t ∈ V, is there a shortest s-t-path in G−F with at most L links? • k-PATH: Does G−F contain a simple path with k links? • k-CLIQUE: Does G−F contain a clique of k nodes? Our main technical contribution is a new construction of (L, f)-replacement path coverings ((L, f)-RPC) in the parameter realm where f = o(log L). An (L, f)-RPC is a family G of subnetworks of G which, for every F ⊆E with |F|< f, has a subfamily GF ⊆G such that (i) no subnetwork in GF contains a link of F and (ii) for each s, t∈V, if G−F contains a shortest s-t-path with at most L links, then some subnetwork in GF retains at least one such path. Our (L, f)-RPC has almost the same size as the one by Weimann and Yuster (2013) but it improves the time to query GF from Oe(f2Lf) to Oe(f25 Lo(1)). It also improves over the size and query time of the (L, f)-RPC by Karthik and Parter (2021) by nearly a factor of L. From this construction, we derive oracles for L-HOP SHORTEST PATH, k-PATH, and k-CLIQUE. Notably, our solution for k-PATH improves the query time of the one by Bilò et al. (2022a) for f = o(log k)
On the Approximability of Graph Visibility Problems
No full textVisibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph G of n vertices asks to find the largest set of vertices X⊆V(G), also called μ-set, such that for any two vertices u,v∈X, there is a shortest u, v-path P where all internal vertices of P are not in X. This means that u and v are visible w.r.t. X. Variations of this problem are known as total, outer, and dual mutual-visibility problems, depending on the visibility property of vertices inside and/or outside X. The mutual-visibility problem and all its variations are known to be NP-complete on graphs of diameter 4. In this paper, we design a polynomial-time algorithm that finds a μ-set with size Ωn/D, where D is the average distance between any two vertices of G. Moreover, we show inapproximability results for all visibility problems on graphs of diameter 2 and strengthen the inapproximability ratios for graphs of diameter 3 or larger. More precisely, for graphs of diameter at least 3 and for every constant ε>0, we show that mutual-visibility and dual mutual-visibility problems are not approximable within a factor of n1/3-ε, while outer and total mutual-visibility problems are not approximable within a factor of n1/2-ε, unless P=NP. Furthermore, in the extended version of this paper we study the relationship between the mutual-visibility number and the general position number in which no three distinct vertices u, v, w of X belong to any shortest path of G
Improved Distance (Sensitivity) Oracles with Subquadratic Space
No full textA distance oracle (DO) for a graph G is a data structure that, when queried with vertices s,t, returns an estimate d(s,t) of their distance in G. The oracle has stretch (α, β) if the estimate satisfies d(s,t)≤ d(s,t)≤ α· d(s,t)+β. An f-edge} fault-tolerant distance sensitivity oracle (f-DSO}) additionally receives a set f of up to f edges and estimates the distance in G-F. Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch β > 0 allows one to make the multiplicative stretch α arbitrarily small. This sidesteps a known lower bound of α≥slant 3 (for β=0 and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in [0, W] that, for any positive integer l and any c\in(0,l/2], has stretch (1+1/l,2W), space O(n2-c/l), and query time O(nc), generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an (α,β)- stretch} DO for unweighted graphs into an (α(1+ε),β)-stretch}. f-DSO} with sensitivity f=o(log(n)/loglog n) retaining sub-quadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [TheoretiCS 2024]. Combining the framework with our new DO gives an f-DSO that, for any γ(0, (l+1)/2], has stretch ((1+1/l)(1+ε), 2), space n2-γ(t+1)(f+1)}+o(1)/εf+2, and query time O(nγ/ε2). This is the first f-DSO} with subquadratic space, near-additive stretch, and sublinear query time
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
