1,721,036 research outputs found
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
A 13/10-approximation Algorithm for Minimum-size 2-Vertex-connectivity of Hamiltonian Graphs
No full textNew 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
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 advances in reoptimizing the minimum Steiner tree problem
No full textIn this paper we improve the results in the literature concerning the problem of computing the minimum Steiner tree given the minimum Steiner tree for a similar problem instance. Using a σ-approximation algorithm computing the minimum Steiner tree from scratch, we provide a and a -approximation algorithm for altering the instance by removing a vertex from the terminal set and by increasing the cost of an edge, respectively. If we use the best up to date σ = ln 4 + ε, our ratios equal 1.218 and 1.279 respectively. © 2012 Springer-Verlag
New reoptimization techniques applied to steiner tree problem
No full textGiven an instance of an optimization problem together with an optimal solution for it, a reoptimization problem asks for a solution for a locally modified input instance. In this paper we develop new reoptimization techniques and apply them to the Steiner Tree Problem. Our techniques significantly improve the previous results and apply to a variety of reoptimization problems. © 2011 Elsevier B.V
Approximating the Metric TSP in Linear Time
No full textGiven a metric graph G = (V,E) of n vertices, i.e., a complete graph with an edge cost function c:V ×V →R ≥ 0 satisfying the triangle inequality, the metricity degree of G is defined as β=maxx,y,z∈V{c(x,y)c(x,z)+c(y,z)}∈[12,1] . This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent traveling salesman problem, which asks for finding a Hamiltonian cycle of G of minimum total cost. In fact, this problem can be approximated quite accurately depending on the metricity degree of G, namely by a ratio of either 2−β3(1−β) or 3β23β2−2β+1 , for β<23 or β≥23 , respectively. Nevertheless, these approximation algorithms have O(n 3) and O(n 2.5 log1.5 n) running time, respectively, and therefore they are superlinear in the Θ(n 2) input size. Thus, since many real-world problems are modeled by graphs of huge size, their use might turn out to be unfeasible in the practice, and alternative approaches requiring only O(n 2) time are sought. However, with this restriction, all the currently available approaches can only guarantee a 2-approximation ratio for the case β= 1, which means a 2β22β2−2β+1 -approximation ratio for general β< 1. In this paper, we show how to enhance –without affecting the space and time complexity– one of these approaches, namely the classic double-MST heuristic, in order to obtain a 2β-approximate solution. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio strictly larger that 2 β, and we further show that any re-elaboration of the shortcutting phase therein provided, cannot lead to a performance ratio better than 2β
Hardness of an Asymmetric 2-player Stackelberg Network Pricing Game
No full textConsider a communication network represented by a directed graph G=(VE) of n nodes and m edges. Assume that edges in E are
partitioned into two sets: a set C of edges with a fixed
non-negative real cost, and a set P of edges whose \emph{price} should instead be set by a \emph{leader}. This is done with the final intent of \emph{maximizing} the payment she will receive for their use by a \emph{follower}, whose goal is to select for his communication purposes a \emph{minimum-cost} (w.r.t. to a given objective function) subnetwork of G. In this paper, we study the natural setting in which the follower computes a \emph{single-source shortest paths tree} of G, and then returns to the leader a payment equal to the \emph{sum} of the selected priceable edges. Thus, the problem can be modeled as a one-round two-player \emph{Stackelberg Network Pricing Game (SNPG)}, with the additional complication that the objective functions of the two players are \emph{asymmetric}. Indeed, the revenue provided to the leader by any of her selected edges is simply its price, while the cost of such an edge in the minimization function of the follower is given by its price multiplied by the number of paths (emanating from the source) it belongs to. As we will see, this asymmetry makes the problem much harder than other previously studied symmetric SNPGs. More precisely, we show that for any 0, unless \p=\np, the problem is not approximable within n12− , while if G is unweighted and the leader can only decide which of her edges enter in the solution, then the problem is not approximable within n13− . On the positive side, when edges in C happen to form the common \emph{unweighted star network} topology, then we show the problem becomes \apx-hard, and admits a 92-approximation algorithm. Furthermore, for general instances, we devise a \emph{strongly} polynomial-time O(n)-approximation algorithm, which favorably compares against the powerful \emph{single-price} algorithm
Augmenting the Edge-Connectivity of a Spider Tree
No full textGiven an undirected, 2-edge-connected, and real weighted graph G, with n vertices and m edges, and given a spanning tree T of G, the 2-edge-connectivity augmentation problem with respect to G and T consists of finding a minimum-weight set of edges of G whose addition to T makes it 2-edge-connected. While the general problem is NP-hard, in this paper we prove that it becomes polynomial time solvable if T can be rooted in such a way that a prescribed topological condition with respect to G is satisfied. In such a case, we provide an O(n(m+h+δ3)) time algorithm for solving the problem, where h and δ are the height and the maximum degree of T, respectively. A faster version of our algorithm can be used for 2-edge connecting a spider tree, that is a tree with at most one vertex of degree greater than two. This finds application in strengthening the reliability of optical networks
Approximating the Metric TSP in Linear Time
No full textGiven a metric graph G=(V,E) of n vertices, i.e., a complete graph with a non-negative real edge cost function satisfying the triangle inequality, the metricity degree of G is defined as β=maxx,y,z∈V{c(x,y)c(x,z)+c(y,z)}∈[12,1] . This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent traveling salesman problem, which asks for finding a Hamiltonian cycle of G of minimum total cost. In fact, this problem can be approximated quite accurately depending on the metricity degree of G, namely by a ratio of either 2−β3(1−β) or 3β23β2−2β+1 , for β0. Our theoretical results are complemented with an extensive series of experiments, that show the practical appeal of our approach
- …
