Given a set $\mathcal{P}$ of $h$ pairwise disjoint simple polygonal obstacles in $\mathbb{R}^2$ defined with $n$ vertices, we compute a sketch $Ω$ of $\mathcal{P}$ whose size is independent of $n$, depending only on $h$ and the input parameter $ε$. We utilize $Ω$ to compute a $(1+ε)$-approximate geodesic shortest path between the two given points in $O(n + h((\lg{n}) + (\lg{h})^{1+δ} + (\frac{1}ε\lg{\frac{h}ε})))$ time. Here, $ε$ is a user parameter, and $δ$ is a small positive constant (resulting from the time for triangulating the free space of $\cal P$ using the algorithm in \cite{journals/ijcga/Bar-YehudaC94}). Moreover, we devise a $(2+ε)$-approximation algorithm to answer two-point Euclidean distance queries for the case of convex polygonal obstacles.

With increase in the number of connected wireless devices, simultaneous use of multiple wireless networks has been proposed as a solution to improve throughput and reduce congestion. The autonomous choice of networks by clients leads to a network selection game, where selfish clients strategize to find the best set of providers. In this network selection game, we define client utility as a function of the throughput achieved when the number of such network connections is constrained. The throughput model is based on capacity sharing and incorporates link dependent PHY rates and priority levels of the clients. This paper studies the stability of the network selection game and provides bounds on the inefficiency of such games. We also present results based on simulation studies.

We consider distributed network routing for networks that support differentiated services, where services are prioritized by a proportional weighting system. We use the classical Generalized Processor Sharing (GPS) scheme for scheduling traffic on network links. In such a scheme, each type of traffic is guaranteed a minimum capacity rate based on its priority. To model the performance of this scheme and to account for autonomous routing we consider scheduling games on networks. We consider both networks with a set of parallel links (which also applies to processor scheduling) and more general scenarios where the network is a multi-graph. In each of these settings we consider two different routing schemes: Atomic and Non-Atomic. Atomic routing requires all traffic of one type to follow a single path. Non-Atomic routing splits traffic into a flow over multiple paths. For each type of game, we prove either the existence of Nash Equilibrium or give a counterexample. We consider the inefficiency of equilibrium (termed as the price of anarchy) and provide price of anarchy upper bounds under reasonable assumptions. In general, this inefficiency in queuing systems is unbounded. We also provide complexity results on computing optimal solutions and the existence of equilibrium in these games.

We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function : the function of prices and income that gives the maximum utility achievable. The formulation is a convex program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies, including: —Homogeneous utilities of degree α ∈ [0, 1] in Fisher economies—this includes Linear, Leontief, Cobb-Douglas — Resource allocation utilities like multi-commodity flows satisfy this condition and can be efficiently solved. Further, we give a natural tâtonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known weak gross substitutes , mimics the natural dynamics for the markets as suggested by Walras: it iteratively adjusts a good’s price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost linear in the number of goods.

In this paper, we consider the inefficiency of distributed routing in a network of parallel links with class-based traffic. Network link behavior is modeled by the M/M/1-GPS queue (i.e. when links use General Processor Sharing(GPS) scheduling scheme to serve packets). Each traffic type is guaranteed a minimum capacity rate on each link using GPS scheduling. We show under specific demand conditions that, among multiple equilibria the worst-case Nash equilibrium occurs when each class dispatcher utilizes all the links to fulfill its demand. Using this fact, we give an upper bound on the Price of Anarchy (PoA). Our results also indicate that, while the price of selfish behavior can be unbounded in a specific demand setting, there exist demand regimes where the bound on PoA is reasonable. These results also apply to the resource allocation or load balancing applications in the processor sharing systems.

In this paper we consider the problem of minimizing delay variance amongst paths utilized for concurrent multi-path routing. We will assume that we are provided with a polynomial size set of paths. Minimizing the variance in the delay will reduce out-of-sequence packets and hence reduce jitter in the received stream. We assume a network with edge delays as well as edge capacities. The edge delays are modelled using constant, affine (including linear) and queueing delays. We show that the problem is NP-hard (even in the case when polynomial-size paths are given and there is no capacity constraint). We also propose a practical heuristic approach and present experimental results on network topologies mimicking large backbone networks.

In this paper we consider the problem of data center allocation to user requests so as to optimize utility of users while satisfying server constraints. The utility or quality of service may be measured as either a required throughput rate or more abstractly in terms of a utility-per-unit of flow. While the typical assignment of a data center to a user is via a matching algorithm, like in Akamai, the use of optimal assignment as well as multiple access paths(as in smart routing in multihoming contexts), allows web services to choose multiple data centers as services. We model the server allocation problem as a graph optimization problem. We propose a ϵ-approximation optimal utility allocation to the fractional version of the problem in this bipartite network. A 1/2-approximation can be obtained from the fractional relaxation. We also design a greedy approach and use it as a basis for comparison. Finally, we present experimental results on an existing ISP network topology.

In this paper we consider the problem of routing traffic between k source-destination pairs. Using game theoretic modeling we provide randomized strategies to minimize the threat of attacks on links by an adversary. The adversary is assumed to have a choice of c edges for attack. We propose iterative methods to find the Nash Equilibrium of the zero-sum game. The proposed schemes have been implemented using existing network models (GEANT in Europe and the AT&T network in US) and show marked reduction in the gain of the attacker. As the gain of the attacker is related to the congestion on the edges, our schemes also reduce congestion.

We study the spectrum market equilibrium where multiple spectrum channels are available, and each of the secondary users has an initial endowment. Assume that each user, with a given endowment, is interested in buying spectrum channels over a specified set of geometric regions in the Euclidean plane. Regions may overlap, thus creating sub- regions where each subregion has a unique set of users interested in acquiring spectrum. Fraction timeshare on spectrum is acceptable. We utilize a price function wherein the price of timeshare on spectrum in a certain region is equal to the maximum price of timeshare amongst the sub-regions in that region. The utility function used is the logarithm utility function. We first prove the existence of equilibrium and then design efficient algorithms for computing the spectrum market equilibrium. We also analyze the utilization of the spectrum by extensive simulations.

One of the most important problems in the field of performance optimization for data networks is the problem of routing to achieve delay minimization. This becomes extremely important in the context of providing Quality of Service while satisfying demand. The problem is classical and was considered three decades ago by a number of authors primarily Gallagher, Bertsekas and Garcia-Luna-Aceves. The models attempt to find multiple flow paths to satisfy demands while minimizing the total delay in the network. Over the years it has become clear that in order to reduce congestion, a multipath approach to routing is needed. Moreover to provide explicit guarantee on QoS the routing needs to provide explicit delay bounds on each flow path. In fact the emergence of voice and video services has highlighted the need for explicit delay bounds. In this paper we propose an iterative algorithm that minimizes the maximum delay for individual flows while meeting demand requirements for multiple source-sink pairs. We assume that the delay on links is a convex function of the demand. We also propose to minimize the gap between the maximum and minimum delay paths so that the buffer required at the destination will be small.

In this paper we address the issue of designing multi-path routing algorithms. Multi-path routing has the potential of improving the throughput but requires buffers at the destination. Our model assumes a network with capacitated edges and a delay function associated with the network links (edges). We consider the problem of establishing a specified throughput from multiple source to destination pairs in the network, given bounds on the buffer sizes available at the network intermediate nodes and a bound on the maximum delay that the paths are allowed to have. We formulate the problem using a linear programming model. We also present practical heuristics and present the experimental results on an existing network topology. The results are promising and demonstrate the effectiveness of simultaneous multipaths in the multi-commodity scenario.

In this paper we address the issue of designing multi-path routing algorithms. Multi-path routing has the potential of improving the throughput but requires buffers at the destination. Our model assumes a network with capacitated edges and a delay function associated with the network links (edges). We consider the problem of establishing a specified throughput from source to destination in the network, given bounds on the buffer size available at the destination and a bound on the maximum delay paths are allowed to have. A related problem which we consider is to establish bounds on the delay variance (which we call jitter) amongst the paths chosen for the multi-path routing scheme. We show that the problems are NP-complete and present pseudo-polynomial algorithms based on linear programming. We also propose practical heuristics and present the experimental results on an existing network topology. The results are promising.

It is desirable to allow packets with the same source and destination to take more than one possible path. This facility can be used to ease congestion and overcome node failures. One approach toward deploying multipath routing in the networks is by creating virtual paths, e.g. using MPLS. There are however costs associated with establishing and maintaining such virtual connections. In this paper, we present the formulation and an approximate solution for the problem of modeling, creation and optimization of the multiple paths in the networks. The aim is to minimize the cost of operating the network and maximize the utilization, using multiple paths. The polynomial-time approximation algorithm presented is based on mixed and linear programming formulation. This approximate solution has a constant approximation ratio; more precisely the throughput of the paths output by our algorithm is at least 0.14 of the optimum throughput, without exceeding the cost of the optimal solution.

In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of items. The market equilibrium problem is to compute a price vector which ensures market clearing, i. e. the demand of a good equals its supply, and given the prices, each buyer maximizes its utility. The problem is of considerable interest in Economics. This paper presents a formulation of the market equilibrium problem as a parameterized linear program. We construct the dual of these parametrized linear programs. We show that finding the market equilibrium is the same as finding a linear-program from the family of programs where the optimal dual solution satisfies certain properties. The market clearing conditions arise naturally from complementary slackness conditions.We then define an auction mechanism which computes prices such that approximate market clearing is achieved. The algorithm we obtain outperforms previously known methods.

Motivated by topology control in ad-hoc wireless networks, power assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). These problems have been studied in the past. In this paper we consider delay bounds as an additional constraint to provide quality of service. Delay is measured by the number of hops on a path between two nodes. We present an algorithm for minimum power bounded hops broadcast with guaranteed bicriteria ratio of (O(log n), O(log n)) for general graphs. That is, in the solution produced by our algorithm, the number of hops between the root and any other node is at most O(log n) times the given bound and the power is at most O(log n) times the power of optimal solution. Our bicriteria results extend to min-power bounded-hops strong connectivity (the solution must have a path of at most d edges in between any two nodes) and min-power bounded-hops symmetric connectivity (the undirected graph having an edge uv iff the solution has both uv and vu is required to have diameter at most d). Previous work for min-power bounded-hops strong connectivity consists only of constant or better approximation for special cases of the Euclidean case. We also provide better guarantees for the Euclidean cases by post processing solutions of the main algorithm.

Multi point routing algorithms capable of satisfying quality of service constraints such as delay boundedness and delay variation boundedness are becoming crucial with the advent of high speed networks. This paper addresses the problem of determining minimum cost paths to nodes in a multicast group satisfying delay bounds and delay variation bounds. A routing protocol is proposed and compared with previous schemes like DVMA (delay variation bounded multicast algorithm). The results show that the scheme proposed improves over the DVMA in the variation bounds achieved and is comparatively far more efficient.

This paper describes an efficient scheme for the dynamic maintenance of the set of maxima of a 2-d set of points. Using the fact that the maxima can be stored in a staircase structure, we use a technique in which we maintain approximations to the staircase structure. We first describe how to maintain the maxima in O(log n) time per insertion and deletion when there are n insertions and deletions. O(log n) is charged per change for reporting changes to the staircase structure which stores the maxima. O(n) space is used. We also show another scheme which requires a total of O(n log n + r) time when r maximal points are listed. We finally consider extensions to higher dimensions.

This paper describes an output-sensitive scheme to construct the visibility graph of a simple polygon with m obstacles and n vertices in optimal O(|E| +T + m log n ) time where |E| is the size of the visibility graph and T is the time required to triangulate the simple polygon with obstacles. We use a partition of the space into regions called corridors which eases the efforts of the construction. Our algorithms are simple and the data structures used are only linked lists.

No abstract available.

This paper describes an efficient algorithm for the geodesic shortest, nath oroblem.i.e. the problem of finding shortest path; bet&n pa& of points on the surface of a 3dimensional polyhedron such that the path is constrained to lie on the surface of the polyhedron.We use the wavefront method and show an O(nlog%) time bound for this problem, when there are O(n) vertices and edges on the polyhedron.

Let S be a set of n points in $\mathbb{R}^D $. It is shown that a range tree can be used to find an $L_\infty $-nearest neighbor in S of any query point in $O((\log n)^{D - 1} \log \log n)$ time. This data structure has size $O(n(\log n)^{D - 1} )$ and an amortized update time of $O((\log n)^{D - 1} \log \log n)$. This result is used to solve the $(1 + \epsilon )$-approximate $L_2 $-nearest-neighbor problem within the same bounds (up to a constant factor that depends on $\epsilon $ and D). In this problem, for any query point p, a point $q \in S$ is computed such that the euclidean distance between p and q is at most $(1 + \epsilon )$ times the euclidean distance between p and its true nearest neighbor. This is the first dynamic data structure for this problem having close to linear size and polylogarithmic query and update times. New dynamic data structures are given that maintain a closest pair of S. For $D \geqslant 3$, a structure of size $O(n)$ is presented with amortized update time $O((\log n)^{D - 1} \log \log n)$. The constant factor in this space (resp. time bound) is of the form $O(D)^D $ (res. $2^{O(D^2 )} $. For $D = 2$ and any nonnegative integer constant k, structures of size $O({{n\log n} / {(\log \log n)^k}} )$ (resp. $O(n)$) are presented that have an amortized update time of $O(\log n\log \log n)$ (resp. $O({{(\log n)^2 } / {(\log \log n)^k}} )$). Previously, no deterministic linear size data structure having polylogarithmic update time was known for this problem.

In this paper, we present algorithms for enumeration of spanning trees in undirected graphs, with and without weights. The algorithms use a search tree technique to construct a computation tree. The computation tree can be used to output all spanning trees by outputting only relative changes between spanning trees rather than the entire spanning trees themselves. Both the construction of the computation tree and the listing of the trees is shown to require $O(N + V + E)$ operations for the case of undirected graphs without weights. The basic algorithm is based on swapping edges in a fundamental cycle. For the case of weighted graphs (undirected), we show that the nodes of the computation tree of spanning trees can be sorted in increasing order of weight, in $O(N \log V + V E)$ time. The spanning trees themselves can be listed in $O(NV)$ time. Here N, V, and E refer, respectively, to the number of spanning trees, vertices, and edges of the graph.

This paper describes an efficient scheme to dynamically maintain the set of maximas of a 2-d set of points. Using the fact that the maximas can be stored in a Staircase structure, we use a technique which maintains approximations to the Staircase structure. We first show how to maintain the maximas in O(logn) time per insertion and deletion when there are n insertions and deletions. O(logn) is charged per change for reporting changes to the structure. We also show another scheme which requires O(logn) amortized time per insertion and deletion with an output complexity of O(r) steps when r maximal points are to be listed. The data structures require O(n) space.

Let S be a set of n points in RD. It is shown that a range tree can be used to find an L∞ -nearest neighbor in S of any query point, in O((logn)D-1 loglogn) time. This data structure has size O(n(logn)D-1) and an amortized update time of O((logn)D-1 loglogn). This result is used to solve the (1+ ϵ)-approximate L2-nearest neighbor problem within the same bounds. In this problem, for any query point p, a point ∈ is computed such that the euclidean distance between p and q is at most (1+ϵ) times the euclidean distance between p and its true nearest neighbor. This is the first dynamic data structure for this problem having close to linear size and polylogarithmic query and update times.

Binary search trees with costs α and β, respectively, on the left and right edges (lopsided search trees) are considered. The exact shape, minimum worst-case cost, and minimum average cost of lopsided trees ofninternal nodes are determined for nonnegative α and β; the costs are both roughly logp(n+ 1) wherepis the unique real number in the interval (1. 2] satisfying 1/pα+ 1/pβ= 1. Search procedures are given that come within a small additive constant of the lower bounds. Almost-optimum algorithms for the lopsided case of unbounded searching are also obtained. Some extensions to nonconstant costs are briefly sketched.

The problem of determining the Euclidean shortest path between two points in the presence of m simple polygonal obstacles is studied. An O( m2 logn + nlogn ) algorithm is developed, where n is the total number of points in the obstacles. A simple O(E+T) algorithm for determining the visibility graph is also shown, where E is the number of visibility edges and T is the time for triangulating the point set. This is extended to a O(Es + nlogn) algorithm for the shortest path problem where Es is bounded by m2.

The problem of finding a rectilinear shortest path amongst obstacles may be stated as follows: Given a set of obstacles in the plane find a shortest rectilinear (L1) path from a point s to a point t which avoids all obstacles. The path may touch an obstacle but may not cross an obstacle. We study the rectilinear shortest path problem for the case where the obstacles are non-intersecting simple polygons, and present an Ο(n (logn)2) algorithm for finding such a path, where n is the number of vertices of the obstacles. We also study the case of rectilinear obstacles in three dimensions, and show that L1 shortest paths can be found in Ο(n2(log n)3) time.

Article Free Access Share on Fast algorithms for convex quadratic programming and multicommodity flows Authors: S Kapoor Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, ILView Profile , P M Vaidya Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, ILView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 147–159https://doi.org/10.1145/12130.12145Published:01 November 1986Publication History 48citation820DownloadsMetricsTotal Citations48Total Downloads820Last 12 Months64Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF