waashk/dblp huggingface dataset:
the effects of temporary sessions on network performance. we consider a packet network, in which packets are injected in sessions along fixed paths. packet movement is restricted by link bandwidth. in case of contention, a contention resolution protocol determines which packets proceed. in the permanent session model, a fixed set of connections is present in the network at all times. in the temporary session model, connections come and go over time. in this paper we compare network performance in these two models in terms of stability and end-to-end delay.we provide the first separation of the two models in terms of stability. in particular, we show that generalized processor sharing (gps) can be unstable with temporary sessions, whereas gps is known to be stable and have polynomial delay bounds with permanent sessions.we also observe that the relative performance of protocols can differ in the two models. for example, in the temporary session model the protocol farthest-to-go (ftg) is known to be stable and therefore outperforms gps. however, in the permanent session model we show that ftg can suffer exponential delays and is therefore outperformed by gps.although polynomial delay bounds are easy to obtain for permanent sessions, this is not the case when sessions can be temporary. we show that a common framework for bounding delays can only lead to superpolynomial bounds in the temporary session model. we also construct superpolynomial lower bounds on delay for a large class of deterministic, distributed protocols that includes the longest-in-system protocol.
scheduling protocols for switches with large envelopes. traditionally, switches make scheduling decisions on the granularity of a packet. however, this is becoming increasingly difficult since network bandwidth is growing rapidly whereas packet sizes remain largely unchanged. therefore the service time of an individual packet is decreasing rapidly. in this paper we study switches that make scheduling decisions on the granularity of an envelope which can be much larger than a packet in size.for an output-queued switch with envelope size e, each output chooses one input every e time steps and transmits packets from this chosen input during the next e steps. for an input-queued switch with envelope size e, one matching from the inputs to the outputs is computed every e steps and only the input---output pairs that are defined by this matching are allowed to transmit packets during the next e steps. traditional switches correspond to envelope size e = 1 and almost all previous scheduling work deals with this case exclusively.we first show how some stable protocols for scheduling networks of output-queued switches with e = 1 fail for arbitrary e when these protocols are generalized in the most straightforward manner. we then present an extremely simple protocol that does guarantee network stability for output-queued switches for any e ¿ 1.for input-queued switches we first present a max-weight matching protocol that is stable for a single switch with arbitrary e. we then present a more complex protocol that achieves stability for a network of input-queued switches for any e ¿ 1.
approximate classification via earthmover metrics. given a metric space (x, d), a natural distance measure on probability distributions over x is the earthmover metric. we use randomized rounding of earthmover metrics to devise new approximation algorithms for two well-known classification problems, namely, metric labeling and 0-extension.our first result is for the 0-extension problem. we show that if the terminal metric is decomposable with parameter &alpha; (e.g., planar metrics are decomposable with &alpha; = o(1)), then the earthmover based linear program (for 0-extension) can be rounded to within an o(&alpha;) factor.our second result is an o(log n)-approximation for metric labeling, using probabilistic tree embeddings in a way very different from the o(log k)-approximation of kleinberg and tardos. (here, n is the number of nodes, and k is the number of labels.) the key element is rounding the earthmover based linear program (for metric labeling) without increasing the solution's cost, when the input graph is a tree. this rounding method also provides an alternate proof to a result stated in chekuri et al., that the earthmover based linear program is integral when the input graph is a tree.our simple and constructive rounding techniques contribute to the understanding of earthmover metrics and may be of independent interest.
an approximate truthful mechanism for combinatorial auctions with single parameter agents. mechanism design seeks algorithms whose inputs are provided by selfish agents who would lie if advantageous. incentive compatible mechanisms compel the agents to tell the truth by making it in their self-interest to do so. often, as in combinatorial auctions, such mechanisms involve the solution of np-hard problems. unfortunately, approximation algorithms typically destroy incentive compatibility. randomized rounding is a commonly used technique for designing approximation algorithms. we devise a version of randomized rounding that is incentive compatible, giving a truthful mechanism for combinatorial auctions with single parameter agents (e.g., "single minded bidders") that approximately maximizes the social value of the auction. we discuss two orthogonal notions of truthfulness for a randomized mechanism, truthfulness with high probability and in expectation, and give a mechanism that achieves both simultaneously.we consider combinatorial auctions where multiple copies of many different items are on sale, and each bidder i desires a subset si. given a set of bids, the problem of finding the allocation of items that maximizes total valuation is the well-known setpacking problem. this problem is np-hard, but for the case of items with many identical copies the optimum can be approximated very well. to turn this approximation algorithm into a truthful auction mechanism we overcome two problems: we show how to make the allocation algorithm monotone, and give a method to compute the appropriate payments efficiently.
faster approximation algorithms for the minimum latency problem. in this paper, we give a 9.28-approximation algorithm for the minimum latency problem that uses only o(n log n) calls to the prize-collecting steiner tree (pcst) subroutine of goemans and williamson. a previous algorithm of goemans and kleinberg for the minimum latency problem requires an approximation algorithm for the k-mst problem which is called as a black box. their algorithm can achieve a performance guarantee of 10.77 while making o(n2 log n) pcst calls (via a k-mst algorithm of garg), or a performance guarantee of 7.18 + &epsilon; while using no(1/&epsilon;) pcst calls (via a k-mst algorithm of arora and karakostas). in order to match our approximation ratio (i.e. setting &epsilon; = 2.10), the latter version requires o(n5 log2 n) pcst calls, so our running time bound is faster by a factor of &theta;(n4 log n). since pcst can be implemented to run in o(n2) time, the overall running time of our algorithm is o(n3 log n).the basic idea for our improvement is that we do not treat the k-mst algorithm as a black box. thus we are able to take advantage of some situations in which the pcst subroutine delivers a k-mst with an improved performance guarantee.
optimal covering tours with turn costs. we give the first algorithmic study of a class of "covering tour" problems related to the geometric traveling salesman problem: find a polygonal tour for a cutter so that it sweeps out a specified region ("pocket") in order to minimize a cost that depends mainly on the number of turns. these problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. we prove the np-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the $m$-guillotine method.
the freeze-tag problem: how to wake up a swarm of robots. an optimization problem that naturally arises in the study of swarm robotics is the freeze-tag problem (ftp) of how to awaken a set of "asleep" robots, by having an awakened robot move to their locations. once a robot is awake, it can assist in awakening other slumbering robots. the objective is to have all robots awake as early as possible. while the ftp bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. we consider both scenarios on graphs and in geometric environments. in graphs, robots sleep at vertices and there is a length function on the edges. awake robots travel along edges, with time depending on edge length. for most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. we prove that the problem is np-hard, even for the special case of star graphs. we also establish hardness of approximation, showing that it is np-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree. these lower bounds are complemented with several positive algorithmic results, including: &#x00b7; we show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (ptas) for star graphs. &#x00b7; we give a simple o(log &#x03b4;)-competitive online algorithm for graphs with maximum degree &#x03b4; and locally bounded edge weights. &#x00b7; we give a ptas, running in nearly linear time, for geometrically embedded instances.
an efficiently computable metric for comparing polygonal shapes. a method for comparing polygons that is a metric, invariant under translation, rotation, and change of scale, reasonably easy to compute, and intuitive is presented. the method is based on the l/sub 2/ distance between the turning functions of the two polygons. it works for both convex and nonconvex polygons and runs in time o(mn log mn), where m is the number of vertices in one polygon and n is the number of vertices in the other. some examples showing that the method produces answers that are intuitively reasonable are presented.
optimal link path queries in a simple polygon. we develop a data structure for answering link distance queries between two arbitrary points in a simple polygon. the data structure requires o(n3) time and space for its construction and answers link distance queries in o(log n) time. our result extends to link distance queries between pairs of segments or polygons. we also propose a simpler data structure for computing a link distance approximately, where the error is bounded by a small additive constant. finally, we also present a scheme for approximating the link and the shortest path distance simultaneously.
temporary tasks assignment resolved. among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. this open problem exists for almost a decade, see [borodin el-yaniv]. we resolve this problem by providing an unapproximability result. in addition, a newer open question is to identify the dependency of the competitive ratio on the durations of jobs in the case where durations are known. we resolve this problem by characterizing this dependency. finally, we provide a ptas for the off-line problem with a fixed number of machines and show a 2 unapproximability for the general case.
on approximating the depth and related problems. in this paper, we study the problem of finding a disk covering the largest number of red points, while avoiding all the blue points. we reduce it to the question of finding a deepest point in an arrangement of pseudodisks and provide a near-linear expected-time randomized approximation algorithm for this problem. as an application of our techniques, we show how to solve linear programming with violations approximately. we also prove that approximate range counting has roughly the same time and space complexity as answering emptiness range queries.
on geometric permutations induced by lines transversal through a fixed point. a line transversal of a family s of n pairwise disjoint convex objects is a straight line meeting all members of s. a geometric permutation of s is the pair of orders in which members of s are met by a line transversal, one order being the reverse of the other.in this note we consider a long-standing open problem in transversal theory, namely that of determining the largest number of geometric permutations that a family of n pairwise disjoint convex objects in rd can admit. we settle a restricted variant of this problem. specifically, we show that the maximum number of those geometric permutations to a family of n > 2 pairwise disjoint convex objects that are induced by lines passing through any fixed point is between k(n - 1, d - 1) and k(n,d - 1), where k(n,d) = &sigma;di=0 (n-1/i) = &theta;(nd) is the number of pairs of antipodal cells in a simple arrangement of n great (d - 1)-spheres in a d-sphere. by a similar argument, we show that the maximum number of connected components of the space of all lines transversal through a fixed point to a family of n > 2 possibly intersecting convex objects is k(n, d - 1). finally, we refute a conjecture of sharir and smorodinsky on the number of neighbor pairs in geometric permutations and offer an alternative conjecture which may be a first step towards solving the aforementioned general problem of bounding the number of geometric permutations.
a randomized online algorithm for bandwidth utilization. protocols for data transmission over an ip computer network should not only lead to efficient network utilization but also be fair to different users. current networks accomplish these goals by some form of end-to-end congestion control. existing protocols, however, assume somewhat altruistic behavior from hosts. karp et al. (2000) have initiated a study of whether or not a single host's optimum strategy (in a system where other hosts are well behaved) is altruistic. we carry this exploration further by developing an efficient randomized algorithm for bandwidth utilization in their model. the competitive ratio of this algorithm is optimal up to a constant factor. karp et al. had earlier studied the deterministic case and left open the randomized case. what may be of some interest is that our algorithm is essentially the classical multiplicative increase, multiplicative decrease strategy, which is very aggressive and non-altruistic.
local versus global properties of metric spaces. motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in l1 with low distortion) are determined by the properties of small subspaces. we note connections to similar issues studied already in ramsey theory, complexity theory (especially pcps), and property testing. we prove both upper bounds and lower bounds on the distortion of embedding locally constrained metrics into various target spaces.
analyzing bittorrent and related peer-to-peer networks. we analyze protocols for disseminating a collection of data blocks over a network of peers with a view towards bit-torrent and related peer-to-peer networks. unlike previous work, we accurately model the distribution of the individual data blocks, a process which is critical to the parallelism that makes bittorrent successful in practice. we also consider multiple network topologies and routing algorithms. we first demonstrate several routing algorithms that distribute b data blocks on a network with diameter d and maximum degree d in o(d(b + d)) phases of concurrent downloads with high probability. this is tight within a factor of d. we also specialize to the networks used by bittorrent and we improve this bound to o(b ln n) phases where n is the number of clients. finally, we discuss several practical extensions to bittorrent, one of which improves the bound to a near-optimal o (b + (ln n)2) phases.
expected-case complexity of approximate nearest neighbor searching. most research in algorithms for geometric query problems has focused on their worst-case performance. however, when information on the query distribution is available, the alternative paradigm of designing and analyzing algorithms from the perspective of expected-case performance appears more attractive. we study the approximate nearest neighbor problem from this perspective.as a first step in this direction, we assume that the query points are sampled uniformly from a hypercube that encloses all the data points; however, we make no assumption on the distribution of the data points. we show that with a simple partition tree, called the sliding-midpoint tree, it is possible to achieve linear space and logarithmic query time in the expected case; in contrast, the data structures known to achieve linear space and logarithmic query time in the worst case are complex, and algorithms on them run more slowly in practice. moreover, we prove that the sliding-midpoint tree achieves optimal expected query time in a certain class of algorithms.
linear-size approximate voronoi diagrams. given a set s of n points in ird, a (t, &epsilon;)-approximate voronoi diagram (avd) is a partition of space into constant complexity cells, where each cell c is associated with t representative points of s, such that for any point in c, one of the associated representatives approximates the nearest neighbor to within a factor of (1 + &epsilon;). the goal is to minimize the number and complexity of the cells in the avd. we show that it is possible to construct an avd consisting of o(n/&epsilon;d) cells for t = 1, and o(n) cells for t = o(1/&epsilon;(d-1)/2). in general, for a real parameter 2 &le; &gamma; &le; 1/&epsilon;, we show that it is possible to construct a (t, &epsilon;)-avd consisting of o(n&gamma;d) cells for t = o(1/(&epsilon;&gamma;)(d-1)/2). the cells in these avds are cubes or differences of two cubes. all these structures can be used to efficiently answer approximate nearest neighbor queries. our algorithms are based on the well-separated pair decomposition and are very simple.
entropy-preserving cuttings and space-efficient planar point location. point location is the problem of preprocessing a planar polygonal subdivision s into a data structure in order to determine efficiently the cell of the subdivision that contains a given query point. given the probabilities pz that the query point lies within each cell z &isin; s, a natural question is how to design such a structure so as to minimize the expected-case query time. the entropy h of the probability distribution is the dominant term in the lower bound on the expected-case search time. clearly the number of edges n of the subdivision is a lower bound on the space required. there is no known approach that simultaneously achieves the goals of h + &ogr;(h) query time and &ogr;(n) space. in this paper we introduce entropy-preserving cuttings and show how to use them to achieve query time h + &ogr;(h), using only &ogr;(n log* n) space.
a simple entropy-based algorithm for planar point location. given a planar polygonal subdivision s, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. suppose that for each cell z in the subdivision, the probability pz that a query point lies within this cell is also given. the goal is to design the data structure to minimize the average search time. this problem has been considered before, but existing data structures are all quite complicated. it has long been known that the entropy h of the probability distribution is the dominant term in the lower bound on the average-case search time. in this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in o(h) average time. we also present empirical evidence for the practical efficiency of this approach.
space-time tradeoffs for approximate spherical range counting. we present space-time tradeoffs for approximate spherical range counting queries. given a set s of n data points in rd along with a positive approximation factor &epsilon;, the goal is to preprocess the points so that, given any euclidean ball b, we can return the number of points of any subset of s that contains all the points within a (1 - &epsilon;)-factor contraction of b, but contains no points that lie outside a (1 + &epsilon;)-factor expansion of b.in many applications of range searching it is desirable to offer a tradeoff between space and query time. we present here the first such tradeoffs for approximate range counting queries. given 0 < &epsilon; &le; 1/2 and a parameter &gamma;, where 2 &le; &gamma; &le; 1/&epsilon;, we show how to construct a data structure of space o(n&gamma;d log (1/&epsilon;)) that allows us to answer &epsilon;-approximate spherical range counting queries in time o(log(n&gamma;) + 1/(&epsilon;&gamma;d-1). the data structure can be built in time o(n&gamma;d log (n/&epsilon;)) log (1/&epsilon;)). here n, &epsilon;, and &gamma; are asymptotic quantities, and the dimension d is assumed to be a fixed constant.at one extreme (low space), this yields a data structure of space o(n log (1/e)) that can answer approximate range queries in time o(logn + 1/(ed-1) which, up to a factor of o(n log (1/e) in space, matches the best known result for approximate spherical range counting queries. at the other extreme (high space), it yields a data structure of space o((n/ed) log(1/&epsilon;)) that can answer queries in time o(logn + 1/&epsilon;). this is the fastest known query time for this problem.we also show how to adapt these data structures to the problem of computing an &epsilon;-approximation to the kth nearest neighbor, where k is any integer from 1 to n given at query time. the space bounds are identical to the range searching results, and the query time is larger only by a factor of o(1/(&epsilon;&gamma;)).our approach is broadly based on methods developed for approximate voronoi diagrams (avds), but it involves a number of significant extensions from the context of nearest neighbor searching to range searching. these include generalizing avd node-separation properties from leaves to internal nodes of the tree and constructing efficient generator sets through a radial decomposition of space. we have also developed new arguments to analyze the time and space requirements in this more general setting.
matrix rounding under the lp-discrepancy measure and its application to digital halftoning. we study the problem of rounding a real-valued matrix into an integer-valued matrix to minimize an lp-discrepancy measure between them. to define the lp-discrepancy measure, we introduce a family ${\cal f}$ of regions (rigid submatrices) of the matrix and consider a hypergraph defined by the family. the difficulty of the problem depends on the choice of the region family ${\cal f}$. we first investigate the rounding problem by using integer programming problems with convex piecewise-linear objective functions and give some nontrivial upper bounds for the lp discrepancy. we propose "laminar family" for constructing a practical and well-solvable class of ${\cal f}$. indeed, we show that the problem is solvable in polynomial time if ${\cal f}$ is the union of two laminar families. finally, we show that the matrix rounding using l1 discrepancy for the union of two laminar families is suitable for developing a high-quality digital-halftoning software.