waashk/dblp huggingface dataset:
biased range trees. a data structure, called a biased range tree, is presented that preprocesses a set s of n points in r2 and a query distribution d for 2-sided orthogonal range counting queries. the expected query time for this data structure, when queries are drawn according to d, matches, to within a constant factor, that of the optimal comparison tree for s and d. the memory and preprocessing requirements of the data structure are o(n log n).
sampling biased lattice configurations using exponential metrics. monotonic surfaces spanning finite regions of zd arise in many contexts, including dna-based self-assembly, card-shuffling and lozenge tilings. we explore how we can sample these surfaces when the distribution is biased to favor higher surfaces. we show that a natural local chain is rapidly mixing with any bias for regions in z2, and for bias &lambda; > d2 in zd, when d > 2. moreover, our bounds on the mixing time are optimal on d-dimensional hyper-cubic regions. the proof uses a geometric distance function and introduces a variant of path coupling in order to handle distances that are exponentially large.
an online mechanism for ad slot reservations with cancellations. many advertisers (bidders) use internet systems to buy display advertisements on publishers' webpages or on traditional media such as radio, tv and newsprint. they seek a simple, online mechanism to reserve ad slots in advance. on the other hand, media publishers (sellers) represent a vast and varying inventory, and they too seek automatic, online mechanisms for pricing and allocating such reservations. we propose and study a simple model for auctioning such ad slot reservations in advance. a seller will display a set of slots at some point t in the future. until t, bidders arrive sequentially and place a bid on the slots they are interested in. the seller must decide immediately whether or not to grant a reservation. our model allows the seller to cancel at any time any reservation made earlier, in which case the holder of the reservation incurs a utility loss amounting to a fraction of her value for the reservation and may also receive a cancellation fee from the seller. our main result is an online mechanism for allocation and pricing in this model with many desirable game-theoretic properties. it is individually rational. winners have an incentive to be honest and bidding one's true value dominates any lower bid. further, it bounds the earnings of speculators who are in the game to obtain the cancellation fees. the mechanism in addition has optimization guarantees. its revenue is within a constant fraction of the a posteriori revenue of the vickrey-clarke-groves (vcg) mechanism which is known to be truthful (in the offline case). our mechanism's efficiency is within a constant fraction of the a posteriori optimally efficient solution. if efficiency also takes into account the utility losses of bidders whose reservation was canceled, we show that our mechanism matches (for appropriate values of the parameters) an upper bound on the competitive ratio of any deterministic online algorithm. our mechanism's technical core is a variant of the online weighted bipartite matching problem where unlike prior variants in which one randomizes edge arrivals or bounds edge weights, we may revoke previously committed edges. our results make no assumptions about bidders' arrival order or value distribution. they still hold if we replace items with elements of a matroid and matchings with independent sets, or if all bidders have additive value for a set of items.
a logarithmic approximation for unsplittable flow on line graphs. we consider the unsplittable flow problem on a line. in this problem, we are given a set of n tasks, each specified by a start time si, an end time ti, a demand di > 0, and a profit pi > 0. a task, if accepted, requires di units of "bandwidth" from time si to ti and accrues a profit of pi. for every time t, we are also specified the available bandwidth ct, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. in this paper, we present the first polynomial-time o(log n)-approximation algorithm for this problem. no polynomial-time o(n)-approximation was known prior to this work. previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called "no-bottleneck" assumption: maxi di &le; mint ct, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. our result, on the other hand, does not require any of these assumptions. our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. while there is an &omega;(n) integrality gap known for this lp relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the lp can in fact be handled using dynamic programming.
towards computing the grothendieck constant. the grothendieck constant kg is the smallest constant such that for every d &isin; n and every matrix a = (aij), [equation] where b(d) is the unit ball in rd. despite several efforts [15, 23], the value of the constant kg remains unknown. the grothendieck constant kg is precisely the integrality gap of a natural sdp relaxation for the km, n-quadratic programming problem. the input to this problem is a matrix a = (aij) and the objective is to maximize the quadratic form &sigma;ij aijxiyj over xiyj &isin; [&minus;1, 1]. in this work, we apply techniques from [22] to the km, n-quadratic programming problem. using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: assuming the unique games conjecture [9], it is np-hard to approximate the km, n-quadratic programming problem to any factor better than the grothendieck constant kg. by adapting a "bootstrapping" argument used in a proof of grothendieck inequality [5], we are able to perform a tighter analysis than [22]. through this careful analysis, we obtain the following new results: &bull; an approximation algorithm for km, n-quadratic programming that is guaranteed to achieve an approximation ratio arbitrarily close to the grothendieck constant kg (optimal approximation ratio assuming the unique games conjecture). &bull; we show that the grothendieck constant kg can be computed within an error &eta;, in time depending only on &eta;. specifically, for each &eta;, we formulate an explicit finite linear program, whose optimum is &eta;-close to the grothendieck constant. we also exhibit a simple family of operators on the gaussian hilbert space that is guaranteed to contain tight examples for the grothendieck inequality.
weighted flow time does not admit o(1)-competitive algorithms. we consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. here, each job j has an arbitrary arrival time rj, weight wj and size pj, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. the first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. in this paper, we show an &omega;(1) lower bound on the competitive ratio of any deterministic online algorithm. our result is based on a gap amplification technique for online algorithms. starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly.
hypergraph regularity and quasi-randomness. thomason and chung, graham, and wilson were the first to systematically study quasi-random graphs and hypergraphs, and proved that several properties of random graphs imply each other in a deterministic sense. their concepts of quasi-randomness match the notion of &epsilon;-regularity from the earlier szemer&eacute;di regularity lemma. in contrast, there exists no "natural" hypergraph regularity lemma matching the notions of quasi-random hypergraphs considered by those authors. we study several notions of quasi-randomness for 3-uniform hypergraphs which correspond to the regularity lemmas of frankl and r&ouml;dl, gowers and haxell, nagle and r&ouml;dl. we establish an equivalence among the three notions of regularity of these lemmas. since the regularity lemma of haxell et al. is algorithmic, we obtain algorithmic versions of the lemmas of frankl-r&ouml;dl (a special case thereof) and gowers as corollaries. as a further corollary, we obtain that the special case of the frankl-r&ouml;dl lemma (which we can make algorithmic) admits a corresponding counting lemma. (this corollary follows by the equivalences and that the regularity lemma of gowers or that of haxell et al. admits a counting lemma.)
the cover time of random geometric graphs. we study the cover time of random geometric graphs. let i(d) = [0, 1]d denote the unit torus in d dimensions. let d(x, r) denote the ball (disc) of radius r. let &upsih;d be the volume of the unit ball d(0, 1) in d dimensions. a random geometric graph g = g(d, r, n) in d dimensions is defined as follows: sample n points v independently and uniformly at random from i(d). for each point x draw a ball d(x, r) of radius r about x. the vertex set v(g) = v and the edge set e(g) = {{v, w}: w &ne; v, w &isin; d(v, r)}. let g(d, r, n), d &ge; 3 be a random geometric graph. let c > 1 be constant, and let r = (c log n/(&upsih;dn))1/d. then whp cg ~ clog(c/c-1)nlogn.
partitioning graphs into balanced components. we consider the k-balanced partitioning problem, where the goal is to partition the vertices of an input graph g into k equally sized components, while minimizing the total weight of the edges connecting different components. we allow k to be part of the input and denote the cardinality of the vertex set by n. this problem is a natural and important generalization of well-known graph partitioning problems, including minimum bisection and minimum balanced cut. we present a (bi-criteria) approximation algorithm achieving an approximation of o(&radic;log n log k), which matches or improves over previous algorithms for all relevant values of k. our algorithm uses a semidefinite relaxation which combines l22 metrics with spreading metrics. surprisingly, we show that the integrality gap of the semidefinite relaxation is &omega;(log k) even for large values of k (e.g., k = n&omega;(1), implying that the dependence on k of the approximation factor is necessary. this is in contrast to previous approximation algorithms for k-balanced partitioning, which are based on linear programming relaxations and their approximation factor is independent of k.
approximate clustering without the approximation. approximation algorithms for clustering points in metric spaces is a flourishing area of research, with much research effort spent on getting a better understanding of the approximation guarantees possible for many objective functions such as k-median, k-means, and min-sum clustering. this quest for better approximation algorithms is further fueled by the implicit hope that these better approximations also yield more accurate clusterings. e.g., for many problems such as clustering proteins by function, or clustering images by subject, there is some unknown correct "target" clustering and the implicit hope is that approximately optimizing these objective functions will in fact produce a clustering that is close pointwise to the truth. in this paper, we show that if we make this implicit assumption explicit---that is, if we assume that any c-approximation to the given clustering objective &phi; is &epsilon;-close to the target---then we can produce clusterings that are o(&epsilon;)-close to the target, even for values c for which obtaining a c-approximation is np-hard. in particular, for k-median and k-means objectives, we show that we can achieve this guarantee for any constant c > 1, and for the min-sum objective we can do this for any constant c > 2. our results also highlight a surprising conceptual difference between assuming that the optimal solution to, say, the k-median objective is &epsilon;-close to the target, and assuming that any approximately optimal solution is &epsilon;-close to the target, even for approximation factor say c = 1.01. in the former case, the problem of finding a solution that is o(&epsilon;)-close to the target remains computationally hard, and yet for the latter we have an efficient algorithm.
self-overlapping curves revisited. let s be a surface embedded in space in such a way that each point has a neighborhood within which the surface is a terrain. then s projects to an immersed surface in the plane, the boundary of which is a (possibly self-intersecting) curve. under what circumstances can we reverse these mappings algorithmically? shor and van wyk considered one such problem, determining whether a curve is the boundary of an immersed disk; they showed that the self-overlapping curves defined in this way can be recognized in polynomial time. we show that several related problems are more difficult: it is np-complete to determine whether an immersed disk is the projection of a disk embedded in space, or whether a curve is the boundary of an immersed surface in the plane that is not constrained to be a disk. however, when a casing is supplied with a self-intersecting curve, describing which component of the curve lies above and which below at each crossing, we may determine in time linear in the number of crossings whether the cased curve forms the projected boundary of a surface in space. as a related result, we show that an immersed surface with a single boundary curve that crosses itself n times has at most 2n/2 combinatorially distinct spatial embeddings, and we discuss the existence of fixed-parameter tractable algorithms for related problems.
an almost (log )-approximation for -connected subgraphs. we consider two cases of the survivable network design (snd) problem: given a complete graph gn = (v, en) with costs on the edges and connectivity requirements {r(u, v): u, v &isin; v}, find a minimum cost subgraph g of gn that contains r(u, v) internally disjoint uv-paths for all u, v &isin; v. our main result is an o (log k &middot; log n/n--k)-approximation algorithm for the k-connected subgraph problem (the case r(u, v) = k for all u, v &isin; v.), for both directed and undirected graphs, where n = |v|. our ratio is o(log k), unless k = n - o(n). previously, the best known approximation guarantees for this problem were o(log2 k) for directed/undirected graphs [kortsarz and nutov stoc 2004, fakcharoenphol and laekhanukit stoc 2008], and o(log k) for undirected graphs with k &le; &radic;n/2 [cheriyan, vempala, and vetta stoc 2002]. as in previous work, we consider the k-connectivity augmentation problem of increasing at minimum cost the connectivity of a given graph j from k - 1 to k; a &rho;-approximation for it is used to derive an o(&rho; &middot; log k)-approximation for k-connected subgraph. fakcharoenphol and laekhanukit showed that k-connectivity augmentation admits an o(log v)-approximation algorithm, where v is the number of minimal "violated" sets in j. however, we may have v = &theta;(n), so this gives only an o(log n)-approximation. we design a novel primal-dual algorithm that adds an edge set of cost &le; opt to get v &le; 2n/n - k. combined with the algorithm of fakcharoenphol and laekhanukit, this gives the ratio o (log n/n - k) for k-connectivity augmentation, which is o(1), unless k = n - o(n). our additional result is for the (undirected) rooted snd, where for a "root" s &isin; v, the connectivity requirements are {r(s, t) = r(t): t &isin; t &sube; v}, and the solution graph should contain r(t) internally disjoint st-paths for all t &isin; t. for large values of k = maxt&isin;t r(t) rooted snd is at least as hard to approximate as directed steiner tree [lando and nutov approx 2008]. for rooted snd [chakraborty, chuzhoy, khanna stoc 08] gave recently a ko(k2) log4 n-approximation algorithm. slightly later [chuzhoy and khanna focs 08] improved the ratio to o(k2 log n), and also gave an o(k8 log2 n)-approximation algorithm for the case of node-costs. independently, we obtained a simple approximation algorithm with ratios o(k2 log n) for edge-costs, and o(k4 log2 n) for node-costs.
combinatorial stochastic processes and nonparametric bayesian modeling. computer science has historically been strong on data structures and weak on inference from data, whereas statistics has historically been weak on data structures and strong on inference from data. one way to draw on the strengths of both disciplines is to develop "inferential methods for data structures"; i.e., methods that update probability distributions on recursively-defined objects such as trees, graphs, grammars and function calls. this is the world of "nonparametric bayes," where prior and posterior distributions are allowed to be general stochastic processes. both statistical and computational considerations lead one to certain classes of stochastic processes, and these tend to have interesting connections to combinatorics. i will give some examples of how this blend of ideas leads to useful models in some applied problem domains, including natural language parsing, computational vision, statistical genetics and protein structural modeling.
secretary problems: weights and discounts. the classical secretary problem studies the problem of selecting online an element (a "secretary") with maximum value in a randomly ordered sequence. the difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. constant-competitive algorithms are known for the classical secretary problems (see, e.g., the survey of freeman [7]) and several variants. we study the following two extensions of the secretary problem: &bull; in the discounted secretary problem, there is a time-dependent "discount" factor d(t), and the benefit derived from selecting an element/secretary e at time t is d(t) &middot; v(e). for this problem with arbitrary (not necessarily decreasing) functions d(t), we show a constant-competitive algorithm when the expected optimum is known in advance. with no prior knowledge, we exhibit a lower bound of &omega;(log n/log log n), and give a nearly-matching o(log n)-competitive algorithm. &bull; in the weighted secretary problem, up to k secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of k positions, with position k having weight w(k), and assigning object/secretary e to position k has benefit w(k) &middot; v(e). the goal is to select secretaries and assign them to positions to maximize &sigma;e, k w(k) &middot; v(e) &middot; xek where xek is an indicator variable that secretary e is assigned position k. we give constant-competitive algorithms for this problem. most of these results can also be extended to the matroid secretary case (babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an o(log rank) loss for general matroids. these results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of babaioff et al. these problems have connections to online mechanism design (see, e.g., hajiaghayi et al. [9]). all our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.
natural algorithms. we provide further evidence that the study of complex self-organizing systems can benefit from an algorithmic perspective. the subject has been traditionally viewed through the lens of physics and control theory. using tools typically associated with theoretical computer science, we settle an old question in theoretical ecology: bounding the convergence of bird flocks. we bound the time to reach steady state by a tower-of-twos of height linear in the number of birds. we prove that, surprisingly, the tower-of-twos growth is intrinsic to the model. this unexpected result demonstrates the merits of approaching biological dynamical systems as "natural algorithms" and applying algorithmic techniques to them.
an efficient sparse regularity concept. let a be a 0/1 matrix of size m x n, and let p be the density of a (i.e., the number of ones divided by m &middot; n). we show that a can be approximated in the cut norm within &epsilon; &middot; mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m &middot; n of a, provided that a satisfies a certain boundedness condition. the decomposition can be computed in polynomial time. this result extends the work of frieze and kannan (combinatorica 1999) to sparse matrices. as an application, we obtain efficient 1 - &epsilon; approximation algorithms for "bounded" instances of max csp problems.
a sense of self for unix processes. a method for anomaly detection is introduced in which ``normal'' is defined by short-range correlations in a process' system calls. initial experiments suggest that the definition is stable during normal behavior for standard unix programs. further, it is able to detect several common intrusions involving sendmail and lpr. this work is part of a research program aimed at building computer security systems that incorporate the mechanisms and algorithms used by natural immune systems.
lomac: low water-mark integrity protection for cots environments. we hypothesize that a form of kernel-resident access-control-based integrity protection can gain widespread acceptance in commercial off-the-shelf (cots) environments if it couples some useful protection with a high degree of compatibility with existing software, configurations, and practices. to test this hypothesis, we have developed a highly compatible free open-source prototype called lomac, and released it on the internet. lomac is a dynamically loadable extension for cots linux kernels that provide integrity protection based on low water-mark access control. we present a classification of existing access control models with regard to compatibility, concluding that models similar to low water-mark are especially well suited to high-compatibility solutions. we also describe our practical strategies for dealing with the pathological cases in the low water-mark model's behavior, which include a small extension of the model, and an unusual application of its concepts.
on confidentiality and algorithms. abstract: recent interest in methods for certifying programs for secure information flow (noninterference) have failed to raise a key question: can efficient algorithms be written so as to satisfy the requirements of secure information flow? in this paper we discuss how algorithms for searching and sorting can be adapted to work on collections of secret data without leaking any confidential information, either directly, indirectly, or through timing behaviour. we pay particular attention to the issue of timing channels caused by cache behaviour, and argue that it is necessary to disable the effect of the cache in order to construct algorithms manipulating pointers to objects in such a way that they satisfy the conditions of noninterference. we also discuss how randomisation can be used to implement secure algorithms, and discuss how randomised hash tables might be made practically secure.
improving computer security using extended static checking. we describe a method for finding security flaws in source code by wayof static analysis.the method is notable because it allows a user tospecify a wide range of security properties while also leveraging aset of predefined common flaws.it works by using an automatedtheorem prover to analyze verification conditions generated from csource code and a set of specifications that define securityproperties.we demonstrate that the method can be used to identifyreal vulnerabilities in real programs.