1,316 research outputs found
New Algorithms for Steiner Tree Reoptimization
No full textReoptimization 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
New bounds for the balloon popping problem
No full textWe reconsider the balloon popping problem, an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixed-price scheme. Previous works show that the optimal solution for this problem is in the range (1.6595,2). We give a new lower bound of 1.68 and design an O(n5) algorithm for computing upper bounds as a function of the number of bidders n . Our algorithm provides an experimental evidence that the correct upper bound is a constant smaller than 2 , thus disproving a currently believed conjecture, and can be used to test the validity of a new conjecture we propose, according to which the upper bound would decrease to π2/6+1/4≈1.8949
New bounds for the balloon popping problem
No full textWe reconsider the balloon popping problem, an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixed-price scheme. Previous works show that the optimal solution for this problem is in the range [1.6595,2]. We give a new lower bound of 1.68 and design an O(n 5) algorithm for computing upper bounds as a function of the number of bidders n. Our algorithm provides an experimental evidence that the correct upper bound is smaller than 2, thus disproving a currently believed conjecture, and can be used to test the validity of a new conjecture we propose, according to which the upper bound would decrease to π 2/6 + 1/4 ≈ 1.8949
Almost Optimal Algorithms for Diameter-Optimally Augmenting Trees
No full textWe consider the problem of augmenting an n-vertex tree with one shortcut in order to minimize the diameter of the resulting graph. The tree is embedded in an unknown space and we have access to an oracle that, when queried on a pair of vertices u and v, reports the weight of the shortcut (u,v) in constant time. Previously, the problem was solved in O(n^2 log^3 n) time for general weights [Oh and Ahn, ISAAC 2016], in O(n^2 log n) time for trees embedded in a metric space [Große et al., https://arxiv.org/abs/1607.05547], and in O(n log n) time for paths embedded in a metric space [Wang, WADS 2017]. Furthermore, a (1+epsilon)-approximation algorithm running in O(n+1/epsilon^3) has been designed for paths embedded in R^d, for constant values of d [Große et al., ICALP 2015].
The contribution of this paper is twofold: we address the problem for trees (not only paths) and we also improve upon all known results. More precisely, we design a time-optimal O(n^2) time algorithm for general weights. Moreover, for trees embedded in a metric space, we design (i) an exact O(n log n) time algorithm and (ii) a (1+epsilon)-approximation algorithm that runs in O(n+ epsilon^{-1}log epsilon^{-1}) time
New algorithms for Steiner tree reoptimization
No full textReoptimization is a setting in which we are given an (near) optimal solution of a problem instance and a local modification that slightly changes the instance. The main goal is that of finding an (near) optimal 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-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 decade. 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
Finding diameter-reducing shortcuts in trees
No full textIn 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 Bounds for the Balloon Popping Problem
No full textWe reconsider the balloon popping problem, an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixed-price scheme. Previous works show that the optimal solution for this problem is in the range [1.6595,2]. We give a new lower bound of 1.68 and design an O(n 5) algorithm for computing upper bounds as a function of the number of bidders n. Our algorithm provides an experimental evidence that the correct upper bound is smaller than 2, thus disproving a currently believed conjecture, and can be used to test the validity of a new conjecture we propose, according to which the upper bound would decrease to π 2/6 + 1/4 ≈ 1.8949. © 2013 Springer-Verlag Berlin Heidelberg
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
No full textGiven a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the fault-tolerant scenario in which each edge e of a given tree spanner may temporarily fail and has to be replaced by a best swap edge, i.e. an edge that reconnects T-e at a minimum stretch factor. More precisely, we design an O(n^2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n^2 log^4 n) time and O(n^2+m log^2n) space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a o(n^2) time and space algorithm would be considered a breakthrough
Almost optimal algorithms for diameter-optimally augmenting trees
No full textWe consider the problem of augmenting an n-vertex tree with one shortcut in order to minimize the diameter of the resulting graph. The tree is embedded in an unknown space and we have access to an oracle that, when queried on a pair of vertices u and v, reports the weight of the shortcut (u,v) in constant time. Previously, the problem was solved in O(n2log3n) time for general weights [Oh and Ahn, ISAAC 2016], in O(n2logn) time for trees embedded in a metric space [Große et al., Int. J. FCS], and in O(nlogn) time for paths embedded in a metric space [Wang, Comput. Geom.]. Very recently an algorithm for general weights requiring O(n2logn) time and O(n) space has been developed [Wang and Zhao, Theor. Comp. Science]. Finally, a (1+ε)-approximation algorithm running in O(n+1/ε3) has been designed for paths embedded in Rd, for constant values of d [Große et al., Int. J. FCS]. In this paper we design an asymptotic time-optimal algorithm for trees and general edge-weights that requires O(n2) time and O(nlogn) space. Moreover, for trees embedded in a metric space, we design (i) an exact O(nlogn)-time algorithm and (ii) a (1+ε)-approximation algorithm that runs in O(n+ε−1logε−1) time
On the tree conjecture for the network creation game
No full textSelfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. (2003) is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all alpha and that for alpha >= n all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bound for the latter conjecture. In particular we show that for alpha > 4n - 13 all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees
- …
