waashk/dblp huggingface dataset:
line-of-sight networks. random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region of the plane (typically a square or circle), and then connects pairs of points by an edge if they are within a fixed distance of one another. in addition to giving rise to a range of basic theoretical questions, this class of random graphs has been a central analytical tool in the wireless networking community. for many of the primary applications of wireless networks, however, the underlying environment has a large number of obstacles, and communication can only take place among nodes when they are close in space and when they have line-of-sight access to one another – consider, for example, urban settings or large indoor environments. in such domains, the standard model of random geometric graphs is not a good approximation of the true constraints, since it is not designed to capture the line-of-sight restrictions. here we propose a random-graph model incorporating both range limitations and line-of-sight constraints, and we prove asymptotically tight results for k-connectivity. specifically, we consider points placed randomly on a grid (or torus), such that each node can see up to a fixed distance along the row and column it belongs to. (we think of the rows and columns as ‘streets’ and ‘avenues’ among a regularly spaced array of obstructions.) further, we show that when the probability of node placement is a constant factor larger than the threshold for connectivity, near-shortest paths between pairs of nodes can be found, with high probability, by an algorithm using only local information. in addition to analysing connectivity and k-connectivity, we also study the emergence of a giant component, as well an approximation question, in which we seek to connect a set of given nodes in such an environment by adding a small set of additional ‘relay’ nodes.
an unbiased pointing operator for unlabeled structures, with applications to counting and sampling. we introduce a general method to count and randomly sample unlabeled combinatorial structures. the approach is based on pointing unlabeled structures in an "unbiased" way, i.e., in such a way that a structure of size n gives rise to n pointed structures. we develop a specific p&oacute;lya theory for the corresponding pointing operator, and present a sampling framework relying both on the principles of boltzmann sampling and on p&oacute;lya operators. our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. the approach applies to unlabeled families of plane and non-plane unrooted trees, and tree-like structures in general, but also to cactus graphs, outerplanar graphs, rna secondary structures, and classes of planar maps.
on the -simple shortest paths problem in weighted directed graphs. we obtain the first approximation algorithm for finding the k-simple shortest paths connecting a pair of vertices in a weighted directed graph. our algorithm is deterministic and has a running time of o(k(m&radic;n + n3/2 log n)) where m is the number of edges in the graph and n is the number of vertices. let s, t &epsilon; v; the length of the i-th simple path from s to t computed by our algorithm is at most 3/2 times the length of the i-th shortest simple path from s to t. the best algorithms for computing the exact k-simple shortest paths connecting a pair of vertices in a weighted directed graph are due to yen [19] and lawler [13]. the running time of their algorithms, using modern data structures, is o(k(mn + n2 log n)). both algorithms are from the early 70's. although this problem and other variants of the k-shortest path problem drew a lot of attention during the last three and a half decades, the o(k(mn + n2 log n)) bound is still unbeaten.
strong price of anarchy. a strong equilibrium (aumann 1959) is a pure nash equilibrium which is resilient to deviations by coalitions. we define the strong price of anarchy to be the ratio of the worst case strong equilibrium to the social optimum. in contrast to the traditional price of anarchy, which quantifies the loss incurred due to both selfishness and lack of coordination, the strong price of anarchy isolates the loss originated from selfishness from that obtained due to lack of coordination. we study the strong price of anarchy in two settings, one of job scheduling and the other of network creation. in the job scheduling game we show that for unrelated machines the strong price of anarchy can be bounded as a function of the number of machines and the size of the coalition. for the network creation game we show that the strong price of anarchy is at most 2. in both cases we show that a strong equilibrium always exists, except for a well defined subset of network creation games.
efficient contention resolution protocols for selfish agents. we seek to understand behavior of selfish agents accessing a broadcast channel. in particular, we consider the natural agent utility where costs are proportional to delay. access to the channel is modelled as a game in extensive form with simultaneous play. standard protocols such as aloha are vulnerable to manipulation by selfish agents. we show that choosing appropriate transmission probabilities for aloha to achieve equilibrium implies exponentially long delays. we give a very simple protocol for the agents that is in nash equilibrium and is also very efficient --- other than with exponentially negligible probability --- all n agents will successfully transmit within cn time, for some small constant c.
a near linear time constant factor approximation for euclidean bichromatic matching (cost). we give an nlogo(1) n-time randomized o(1)-approximation algorithm for computing the cost of minimum bichromatic matching between two planar point-sets of size n.
embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. this paper addresses the basic question of how well can a tree approximate distances of a metric space or a graph. given a graph, the problem of constructing a spanning tree in a graph which strongly preserves distances in the graph is a fundamental problem in network design. we present scaling distortion embeddings where the distortion scales as a function of &epsilon;, with the guarantee that for each &epsilon; the distortion of a fraction 1 - &epsilon; of all pairs is bounded accordingly. such a bound implies, in particular, that the average distortion and lq-distortions are small. specifically, our embeddings have constant average distortion and o(&radic;log n) l2-distortion. this follows from the following results: we prove that any metric space embeds into an ultrametric with scaling distortion o(&radic;1/&epsilon;). for the graph setting we prove that any weighted graph contains a spanning tree with scaling distortion o(&radic;1/&epsilon;). these bounds are tight even for embedding in arbitrary trees. for probabilistic embedding into spanning trees we prove a scaling distortion of &otilde;(log2(1/&epsilon;)), which implies constant lq-distortion for every fixed q < &infin;.
dynamic pricing for impatient bidders. we study the following problem related to pricing over time. assume there is a collection of bidders, each of whom is interested in buying a copy of an item of which there is an unlimited supply. every bidder is associated with a time interval over which the bidder will consider buying a copy of the item, and a maximum value the bidder is willing to pay for the item. on every time unit, the seller sets a price for the item. the seller's goal is to set the prices so as to maximize revenue from the sale of copies of items over the time period. in the first model considered, we assume that all bidders are impatient, that is, bidders buy the item at the first time unit within their bid interval that they can afford the price. to the best of our knowledge, this is the first work that considers this model. in the offline setting, we assume that the seller knows the bids of all the bidders in advance. in the online setting we assume that at each time unit the seller only knows the values of the bids that have arrived before or at that time unit. we give a polynomial time offline algorithm and prove upper and lower bounds on the competitiveness of deterministic and randomized online algorithms, compared with the optimal offline solution. the gap between the upper and lower bounds is quadratic. we also consider the envy-free model in which bidders are sold the item at the minimum price during their bid interval, as long as it is not over their limit value. we prove tight bounds on the competitiveness of deterministic online algorithms for this model, and upper and lower bounds on the competitiveness of randomized algorithms with quadratic gap. the lower bounds for the randomized case in both models use a novel general technique.
aggregation of partial rankings, -ratings and top- lists. we study the problem of aggregating partial rankings. this problem is motivated by applications such as meta-searching and information retrieval, search engine spam fighting, e-commerce, learning from experts, analysis of population preference sampling, committee decision making and more. we improve recent constant factor approximation algorithms for aggregation of full rankings and generalize them to partial rankings. our algorithms improve constant factor approximation with respect to a family of metrics recently proposed in the context of comparing partial rankings. we pay special attention to two important types of partial rankings: the well-known top-m lists and the more general p-ratings which we define. we provide first evidence for hardness of aggregating them for constant&#x00a0;m,&#x00a0;p.
pull-based data broadcast with dependencies: be fair to users, not to items. broadcasting is known to be an efficient means of disseminating data in wireless communication environments (such as satellite, mobile phone networks,...). it has been recently observed that the average service time of broadcast systems can be considerably improved by taking into consideration existing correlations between requests. we study a pull-based data broadcast system where users request possibly overlapping sets of items; a request is served when all its requested items are downloaded. we aim at minimizing the average user perceived latency, i.e. the average flow time of the requests. we first show that any algorithm that ignores the dependencies can yield arbitrary bad performances with respect to the optimum even if it is given arbitrary extra resources. we then design a (4 + &epsilon;)-speed o(1 + 1/&epsilon;2)-competitive algorithm for this setting that consists in 1) splitting evenly the bandwidth among each requested set and in 2) broadcasting arbitrarily the items still missing in each set into the bandwidth the set has received. our algorithm presents several interesting features: it is simple to implement, non-clairvoyant, fair to users so that no user may starve for a long period of time, and guarantees good performances in presence of correlations between user requests (without any change in the broadcast protocol). we also present a (4 + &epsilon;)-speed o(1 + 1/&epsilon;3)-competitive algorithm which broad-casts at most one item at any given time and preempts each item broadcast at most once on average. as a side result of our analysis, we design a competitive algorithm for a particular setting of non-clairvoyant job scheduling with dependencies, which might be of independent interest.1
island hopping and path colouring with applications to wdm network design. wavelength division multiplexed (wdm) optical communication offers the advantages of increased capacity and decreased latency for signals (traffic) carried across such networks. the devices used for "switching", however, force additional constraints on the mathematical design of such networks. in this paper we explore two such constaints: (i) optical lightpaths must be assigned individual wavelengths and (ii) sometimes lightpaths must unavoidably go through an optical-electronic-optical (oeo) conversion by means of an expensive piece of equipment called an optical transponder. we term the graph theoretical problems related to these constraints path colouring and island hopping. we present a range of upper and lower bounds for these problems. in particular, we extend the work of winkler and zhang (2003) and anshelevich and zhang (2004).
compacting cuts: a new linear formulation for minimum cut. for a graph (v,e), existing compact linear formulations for the minimum cut problem require &theta;(&verbar;v&verbar;&verbar;e&verbar;) variables and constraints and can be interpreted as a composition of &verbar;v&verbar; &minus; 1 polyhedra for minimum s-t cuts in much the same way as early approaches to finding globally minimum cuts relied on &verbar;v&verbar; &minus; 1 calls to a minimum s-t cut algorithm. we present the first formulation to beat this bound, one that uses o(&verbar;v&verbar;2) variables and o(&verbar;v&verbar;3) constraints. an immediate consequence of our result is a compact linear relaxation with o(&verbar;v&verbar;2) constraints and o(&verbar;v&verbar;3) variables for enforcing global connectivity constraints. this relaxation is as strong as standard cut-based relaxations and has applications in solving traveling salesman problems by integer programming as well as finding approximate solutions for survivable network design problems using jain's iterative rounding method. another application is a polynomial-time verifiable certificate of size n for for the np-complete problem of l1-embeddability of a rational metric on an n-set (as opposed to a certificate of size n2 known previously).
a ptas for tsp with neighborhoods among fat regions in the plane. the euclidean tsp with neighborhoods (tspn) problem seeks a shortest tour that visits a given collection of n regions (neighborhoods). we present the first polynomial-time approximation scheme for tspn for a set of regions given by arbitrary disjoint fat regions in the plane. this improves substantially upon the known approximation algorithms, and is the first ptas for tspn on regions of non-comparable sizes. our result is based on a novel extension of the m-guillotine method. the result applies to regions that are "fat" in a very weak sense: each region pi contains a disk of radius &omega;(diam(pi)), but is otherwise arbitrary. further, the result applies even if the regions intersect arbitrarily, provided that there exists a packing of disjoint disks, of radii &omega;(diam(pi)), contained within their respective regions. finally, the ptas result applies also to the case in which the regions are sets of points or polygons, each each lying within one of a given set of disjoint fat regions.
tree exploration with logarithmic memory. we consider the task of network exploration by a mobile agent (robot) with small memory. the agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. nodes of the network are unlabeled and edge ports are locally labeled at each node. the agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. we present an algorithm to accomplish tree exploration (with return) using o(log n)-bit memory for all n-node trees. this strengthens the result from [15], where o(log2 n)-bit memory was used for tree exploration, and matches the lower bound on memory size proved there.
on the number of tetrahedra with minimum, unit, and distinct volumes in three-space. we formulate and give partial answers to several combinatorial problems on volumes of simplices determined by n points in 3-space, and in general in d dimensions. <label>(i)</label>the number of tetrahedra of minimum (non-zero) volume spanned by n points in <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline1"><alt-text>$\mathbb{r}$</alt-text></inline-graphic>3 is at most <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline2"><alt-text>$\frac{2}{3}n^3-o(n^2)$</alt-text></inline-graphic>, and there are point sets for which this number is <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline3"><alt-text>$\frac{3}{16}n^3-o(n^2)$</alt-text></inline-graphic>. we also present an o(n3) time algorithm for reporting all tetrahedra of minimum non-zero volume, and thereby extend an algorithm of edelsbrunner, o'rourke and seidel. in general, for every <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline4"><alt-text>$k,d\in \mathbb{n}, 1\leq k \leq d$</alt-text></inline-graphic>, the maximum number of k-dimensional simplices of minimum (non-zero) volume spanned by n points in <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline1"><alt-text>$\mathbb{r}$</alt-text></inline-graphic>d is θ(nk). <label>(ii)</label>the number of unit volume tetrahedra determined by n points in <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline1"><alt-text>$\mathbb{r}$</alt-text></inline-graphic>3 is o(n7/2), and there are point sets for which this number is ω(n3 log logn). <label>(iii)</label>for every <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline5"><alt-text>$d\in \mathbb{n}$</alt-text></inline-graphic>, the minimum number of distinct volumes of all full-dimensional simplices determined by n points in <inline-graphic mime-subtype="gif" xlink="s096354830700884x_inline1"><alt-text>$\mathbb{r}$</alt-text></inline-graphic>d, not all on a hyperplane, is θ(n).
fractional packing in ideal clutters. in this paper we present a polyhedral framework for fractional packing in ideal clutters. consider an ideal clutter with a nonnegative capacity function on its vertices. it follows from ideality that for any nonnegative capacity the total multiplicity of an optimal fractional packing is equal to the minimum capacity of a vertex cover. our framework finds an optimal packing using at most n edges with positive multiplicities, performing at most n times minimizations for the clutter and at most n2 times minimizations for its blocker, where n denotes the cardinality of the vertex set. applied to the clutter of dijoins (directed cut covers), the framework provides the first combinatorial polynomial-time algorithm for fractional packing of dijoins.
zone diagrams: existence, uniqueness and algorithmic challenge. a zone diagram is a new variation of the classical notion of the voronoi diagram. given points (sites) ${\mathbf p}_1,\ldots,{\mathbf p}_n$ in the plane, each ${\mathbf p}_i$ is assigned a region $r_i$, but in contrast to the ordinary voronoi diagrams, the union of the $r_i$ has a nonempty complement, the neutral zone. the defining property is that each $r_i$ consists of all ${\mathbf x}\in{\mathbb{r}}^2$ that lie closer (nonstrictly) to ${\mathbf p}_i$ than to the union of all the other $r_j$, $j\ne i$. thus, the zone diagram is defined implicitly, by a &ldquo;fixed-point property,&rdquo; and neither its existence nor its uniqueness seem obvious. we establish existence using a general fixed-point result (a consequence of schauder's theorem or kakutani's theorem); this proof should generalize easily to related settings, say higher dimensions. then we prove uniqueness of the zone diagram, as well as convergence of a natural iterative algorithm for computing it, by a geometric argument, which also relies on a result for the case of two sites in an earlier paper. many challenging questions remain open.
reconstruction using witness complexes. we present a novel reconstruction algorithm that, given an input point set sampled from an object s, builds a one-parameter family of complexes that approximate s at different scales. at a high level, our method is very similar in spirit to chew's surface meshing algorithm, with one notable difference: the restricted delaunay triangulation is replaced by the witness complex, which makes our algorithm applicable in any metric space. to prove its correctness on curves and surfaces, we highlight the relationship between the witness complex and the restricted delaunay triangulation in 2d and in 3d. specifically, we prove that both complexes are equal in 2d and closely related in 3d, under some mild sampling assumptions.
a rigorous analysis of population stratification with limited data. finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. one of the major difficulties in these studies, is the fact that the genetic components of an individual not only depend on the disease, but also on its ethnicity. therefore, it is crucial to find methods that could reduce the population structure effects on these studies. this can be formalized as a clustering problem, where the individuals are clustered according to their genetic information. mathematically, we consider the problem of clustering bit "feature" vectors, where each vector represents the genetic information of an individual. our model assumes that this bit vector is generated according to a prior probability distribution specified by the individual's membership in a population. we present methods that can cluster the vectors while attempting to optimize the number of features required. the focus of the paper is not on the algorithms, but on showing that optimizing certain objective functions on the data yields the right clustering, under the random generative model. in particular, we prove that some of the previous formulations for clustering are effective. we consider two different clustering approaches. the first approach forms a graph, and then clusters the data using a connected components algorithm, or a max cut algorithm. the second approach tries to estimate simultanously the feature frequencies in each of the populations, and the classification of vectors into populations. we show that using the first approach &theta;(logn/&gamma;2) data (i.e., total number of features times number of vectors) is sufficient to find the correct classification, where n is the number of vectors of each population, and &gamma; is the average l22 distance between the feature probability vectors of the two populations. using the second approach, we show that o(log n/&alpha;4) data is enough, where &alpha; is the average l1 distance between the populations. we also present polynomial time algorithms for the resulting max margin which, for now, needs only slightly more data than stated above. our methods can also be used to give a simple combinatorial algorithm for finding a bisection in a random graph that matches boppana's convex programming approach (and mcsherry's spectral results).