Search

We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or STACKMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player's best strategy in STACKMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min{k, 3 + 2 In 6,1 + In W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm. © Springer-Verlag Berlin Heidelberg 2007., Frank Dehne, Jörg-Rüdiger Sack, and Norbert Zeh, editors, Algorithms and Data Structures, Springer Berlin / Heidelberg, 10th International Workshop on Algorithms and Data Structures, WADS 2007; Halifax; Canada; 15 August 2007 through 17 August 2007., info:eu-repo/semantics/published

We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or STACKMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player's best strategy in STACKMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min{k, 3 + 2 In 6,1 + In W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm. © Springer-Verlag Berlin Heidelberg 2007., Frank Dehne, Jörg-Rüdiger Sack, and Norbert Zeh, editors, Algorithms and Data Structures, Springer Berlin / Heidelberg, 10th International Workshop on Algorithms and Data Structures, WADS 2007; Halifax; Canada; 15 August 2007 through 17 August 2007., info:eu-repo/semantics/published

We consider a coloring problem on dynamic, one-dimensional point sets: points appearing and disappearing on a line at given times. We wish to color them with k colors so that at any time, any sequence of p(k) consecutive points, for some function p, contains at least one point of each color. We prove that no such function p(k) exists in general. However, in the restricted case in which points appear gradually, but never disappear, we give a coloring algorithm guaranteeing the property at any time with p(k)=3k-2. This can be interpreted as coloring point sets in R^2 with k colors such that any bottomless rectangle containing at least 3k-2 points contains at least one point of each color. Here a bottomless rectangle is an axis-aligned rectangle whose bottom edge is below the lowest point of the set. For this problem, we also prove a lower bound p(k)>ck, where c>1.67. Hence for every k there exists a point set, every k-coloring of which is such that there exists a bottomless rectangle containing ck points and missing at least one of the k colors. Chen et al. (2009) proved that no such function $p(k)$ exists in the case of general axis-aligned rectangles. Our result also complements recent results from Keszegh and Palvolgyi on cover-decomposability of octants (2011, 2012)., Comment: A preliminary version was presented by a subset of the authors to the European Workshop on Computational Geometry, held in Assisi (Italy) on March 19-21, 2012

Link to conference publication published by Springer: http://dx.doi.org/10.1007/978-3-642-03367-4, We show that if one can find the optimal value of an integer linear programming problem in polynomial time, then one can find an optimal solution in polynomial time. We also present a proper generalization to (general) integer programs and to local search problems of the well-known result that optimization and augmentation are equivalent for 0/1-integer programs. Among other things, our results imply that PLS-complete problems cannot have “near-exact” neighborhoods, unless PLS = P., United States. Office of Naval Research (ONR grant N00014-01208-1-0029)

Let $G=(S, E)$ be a plane straight-line graph on a finite point set $S\subset\R^2$ in general position. The incident angles of a vertex $p \in S$ of $G$ are the angles between any two edges of $G$ that appear consecutively in the circular order of the edges incident to $p$. A plane straight-line graph is called $\phi$-open if each vertex has an incident angle of size at least $\phi$. In this paper we study the following type of question: What is the maximum angle $\phi$ such that for any finite set $S\subset\R^2$ of points in general position we can find a graph from a certain class of graphs on $S$ that is $\phi$-open? In particular, we consider the classes of triangulations, spanning trees, and paths on $S$ and give tight bounds in most cases., Comment: 15 pages, 14 figures. Apart of minor corrections, some proofs that were omitted in the previous version are now included