waashk/dblp huggingface dataset:
maximum independent set of rectangles. we study the maximum independent set of rectangles (misr) problem: given a collection r of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles. misr is a special case of the classical maximum independent set problem, where the input is restricted to intersection graphs of axis-parallel rectangles. due to its many applications, ranging from map labeling to data mining, misr has received a significant amount of attention from various research communities. since the problem is np-hard, the main focus has been on the design of approximation algorithms. several groups of researches have independently suggested o(log n)-approximation algorithms for misr, and this remained the best currently known approximation factor for the problem. the main result of our paper is an o(log log n)-approximation algorithm for misr. our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in the plane. we also consider a generalization of misr to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. our results for misr imply an o((log n)d&minus;2 log log n)-approximation algorithm for this problem, improving upon the best previously known o((log n)d&minus;1)-approximation.
almost all hypergraphs without fano planes are bipartite. the hypergraph of the fano plane is the unique 3-uniform hypergraph with 7 triples on 7 vertices in which every pair of vertices is contained in a unique triple. this hypergraph is not 2-colorable, but becomes so on deleting any hyperedge from it. we show that taking uniformly at random a labeled 3-uniform hypergraph h on n vertices not containing the hypergraph of the fano plane, h turns out to be 2-colorable with probability at least 1 -- 2-&omega;(n2). for the proof of this result we will study structural properties of fano-free hypergraphs.
fast edge orientation for unweighted graphs. we consider an unweighted undirected graph with n vertices, m edges, and edge-connectivity 2k. the weak edge orientation problem requires that the edges of this graph be oriented so the resulting directed graph is at least k edge-connected. nash-williams proved the existence of such orientations and subsequently frank [6], gabow [7], and nagamochi-ibaraki [12] gave algorithmic constructions. all of these algorithms took time at least quadratic in n. we provide the first sub-quadratic (in n) algorithm for this problem. our algorithm takes &otilde;(nk4 + m) time. this improves the previous best bounds of &otilde;(n2k2 + m) by gabow [7] and &otilde;(n2m) by nagamochi-ibaraki [12] when k &le; &radic;n. indeed, many real networks have k &lt; n. our algorithm uses the fast edge splitting paradigm introduced by bhalgat et al. [2]. we seek to split out a large fraction of the vertices, recurse on the resulting graph, and then put back the split-off vertices. the main challenge we face is that only vertices with even degree may be split-off in an undirected graph and there may not be any such vertex in the current graph. the edge orientation algorithms of gabow and nagamochi-ibaraki as well as frank's proof are based on showing the existence of at least two even degree vertices (in fact, vertices with degree 2k) in a 2k minimally connected graph. we generalize this to show that in any edge minimal 2k edge-connected graph, there are at least n/3 even degree vertices. these vertices are then split-off. our next challenge is to drop edges from the given graph so it remains 2k connected and yet has &omega;(n) even degree vertices. we provide an algorithm that discards edges specifically to produce &omega;(n) even degree vertices while maintaining connectivity 2k and takes time &otilde;(nk4 + m). note that this algorithm does not necessarily make the graph edge-minimally 2k edge-connected. we also briefly outline an &otilde;(nk5 + m) time algorithm that achieves edge-minimality which improves the previous best bound of &otilde;(m + n2k2) by gabow [7].
speed scaling with an arbitrary power function. all of the theoretical speed scaling research to date has assumed that the power function, which expresses the power consumption p as a function of the processor speed s, is of the form p = s&alpha;, where &alpha; > 1 is some constant. motivated in part by technological advances, we initiate a study of speed scaling with arbitrary power functions. we consider the problem of minimizing the total flow plus energy. our main result is a (3+&epsilon;)-competitive algorithm for this problem, that holds for essentially any power function. we also give a (2+&epsilon;)-competitive algorithm for the objective of fractional weighted flow plus energy. even for power functions of the form s&alpha;, it was not previously known how to obtain competitiveness independent of &alpha; for these problems. we also introduce a model of allowable speeds that generalizes all known models in the literature.
analysis of scalar fields over point cloud data. given a real-valued function f defined over some metric space x, is it possible to recover some structural information about f from the sole information of its values at a finite set l &sube; x of sample points, whose pairwise distances in x are given? we provide a positive answer to this question. more precisely, taking advantage of recent advances on the front of stability for persistence diagrams, we introduce a novel algebraic construction, based on a pair of nested families of simplicial complexes built on top of the point cloud l, from which the persistence diagram of f can be faithfully approximated. we derive from this construction a series of algorithms for the analysis of scalar fields from point cloud data. these algorithms are simple and easy to implement, have reasonable complexities, and come with theoretical guarantees. to illustrate the generality of the approach, we present some experimental results obtained in various applications, ranging from clustering to sensor networks (see the electronic version of the paper for color pictures).
appointment scheduling with discrete random durations. we consider the problem of determining optimal appointment schedule for a given sequence of jobs (e.g., medical procedures) on a single processor (e.g., operating room, examination facility), to minimize the expected total underage and overage costs when each job has a random processing duration given by a joint discrete probability distribution. simple conditions on the cost rates imply that the objective function is submodular and l-convex. then there exists an optimal appointment schedule which is integer and can be found in polynomial time. our model can handle a given due date for the total processing (e.g., end of day for an operating room) after which overtime is incurred and, no-shows and emergencies.
combinatorial algorithms for nearest neighbors, near-duplicates and small-world design. we study the so called combinatorial framework for algorithmic problems in similarity spaces. namely, the input dataset is represented by a comparison oracle that given three points x, y, y' answers whether y or y' is closer to x. we assume that the similarity order of the dataset satisfies the four variations of the following disorder inequality: if x is the a'th most similar object to y and y is the b'th most similar object to z, then x is among the d(a + b) most similar objects to z, where d is a relatively small disorder constant. though the oracle gives much less information compared to the standard general metric space model where distance values are given, one can still design very efficient algorithms for various fundamental computational tasks. for nearest neighbor search we present deterministic and exact algorithm with almost linear time and space complexity of preprocessing, and near-logarithmic time complexity of search. then, for near-duplicate detection we present the first known deterministic algorithm that requires just near-linear time + time proportional to the size of output. finally, we show that for any dataset satisfying the disorder inequality a visibility graph can be constructed: all outdegrees are near-logarithmic and greedy routing deterministically converges to the nearest neighbor of a target in logarithmic number of steps. the later result is the first known work-around for navarro's impossibility of generalizing delaunay graphs. the technical contribution of the paper consists of handling "false positives" in data structures and an algorithmic technique up-aside-down-filter.
testing halfspaces. this paper addresses the problem of testing whether a boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w &middot; x - &theta;). we consider halfspaces over the continuous domain rn (endowed with the standard multivariate gaussian distribution) as well as halfspaces over the boolean cube {&minus;1, 1}n (endowed with the uniform distribution). in both cases we give an algorithm that distinguishes halfspaces from functions that are &epsilon;-far from any halfspace using only poly(1/&epsilon;) queries, independent of the dimension n. two simple structural results about halfspaces are at the heart of our approach for the gaussian distribution: the first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. we prove analogous results for the boolean cube {&minus;1, 1}n (with fourier coefficients in place of hermite coefficients) for balanced halfspaces in which all degree-1 fourier coefficients are small. dealing with general halfspaces over {&minus;1, 1}n poses significant additional complications and requires other ingredients. these include "cross-consistency" versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [fkr+02].
packing multiway cuts in capacitated graphs. we consider the following "multiway cut packing" problem in undirected graphs: given a graph g = (v, e) and k commodities, each corresponding to a set of terminals located at different vertices in the graph, our goal is to produce a collection of cuts {e1, ..., ek} such that ei is a multiway cut for commodity i and the maximum load on any edge is minimized. the load on an edge is defined to be the number of cuts in the solution containing the edge. in the capacitated version of the problem the goal is to minimize the maximum relative load on any edge---the ratio of the edge's load to its capacity. multiway cut packing arises in the context of graph labeling problems where we are given a partial labeling of a set of items and a neighborhood structure over them, and the goal, informally stated, is to complete the labeling in the most consistent way. this problem was introduced by rabani, schulman, and swamy (soda'08), who developed an o(log n/log log n) approximation for it in general graphs, as well as an improved o(log2 k) approximation in trees. here n is the number of nodes in the graph. we present the first constant factor approximation for this problem in arbitrary undirected graphs. our lp-rounding-based algorithm guarantees a maximum edge load of at most 8opt + 4 in general graphs. our approach is based on the observation that every instance of the problem admits a laminar solution (that is, no pair of cuts in the solution crosses) that is near-optimal.
a unified approach to distance-two colouring of planar graphs. we introduce the notion of (a, b)-colouring of a graph: for given vertex sets a, b, this is a colouring of the vertices in b so that both adjacent vertices and vertices with a common neighbour in a receive different colours. this concept generalises the notion of colouring the square of graphs and of cyclic colouring of plane graphs. we prove a general result which implies asymptotic versions of wegner's and borodin's conjecture on these two colourings. using a recent approach of havet et al., we reduce the problem to edge-colouring of multigraphs and then use kahn's result that the list chromatic index is close from the fractional chromatic index. our results are based on a strong structural lemma for planar graphs which also implies that the size of a clique in the square of a planar graph of maximum degree &delta; is at most 3/2 &delta; plus a constant.
the uniform hardcore lemma via approximate bregman projections. we give a simple, more efficient and uniform proof of the hard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryptography. our result follows from the connection between boosting algorithms and hard-core set constructions discovered by klivans and servedio [11]. informally stated, our result is the following: suppose we fix a family of boolean functions. assume there is an efficient algorithm which for every input length and every smooth distribution (i.e. one that doesn't assign too much weight to any single input) over the inputs produces a circuit such that the circuit computes the boolean function noticeably better than random. then, there is an efficient algorithm which for every input length produces a circuit that computes the function correctly on almost all inputs. our algorithm significantly simplifies previous proofs of the uniform and the non-uniform hard-core lemma, while matching or improving the previously best known parameters. the algorithm uses a generalized multiplicative update rule combined with a natural notion of approximate bregman projection. bregman projections are widely used in convex optimization and machine learning. we present an algorithm which efficiently approximates the bregman projection onto the set of high density measures when the kullback-leibler divergence is used as a distance function. our algorithm has a logarithmic runtime over any domain from which we can efficiently sample. high density measures correspond to smooth distributions which arise naturally, for instance, in the context of online learning. hence, our technique may be of independent interest.
stepwise randomized combinatorial auctions achieve revenue monotonicity. in combinatorial auctions that use vcg, a seller can sometimes increase revenue by dropping bidders (see e.g. [5]). in our previous work [26], we showed that such failures of "revenue monotonicity" occur under an extremely broad range of deterministic strategyproof combinatorial auction mechanisms, even when bidders have "known single-minded" valuations. in this work we consider the question of whether revenue monotonic, strategyproof mechanisms for such bidders can be found in the broader class of randomized mechanisms. we demonstrate that---surprisingly- such mechanisms do exist, show how they can be constructed, and consider algorithmic techniques for implementing them in polynomial time. more formally, we characterize a class of randomized mechanisms defined for known single-minded bidders that are strategyproof and revenue monotonic, and furthermore satisfy some other desirable properties, namely participation, consumer sovereignty and maximality, representing the mechanism as a solution to a quadratically constrained linear program (qclp). we prove that the qclp is always feasible (i.e., for all bidder valuations) and give its solution analytically. furthermore, we give an algorithm for running such a mechanism in time polynomial in the number of bidders and goods; this is interesting because constructing an instance of such mechanisms from our qclp formulation in a naive way can require exponential time.
a nearly linear time algorithm for the half integral parity disjoint paths packing problem. we consider the following problem, which is called the half integral parity disjoint paths packing problem. input: a graph g, k pair of vertices (s1, t1), (s2, t2), ...,(sk, tk) in g (which are sometimes called terminals), and a parity li for each i with 1 &le; i &le; k, where li = 0 or 1. output: paths p1, ..., pk in g such that pi joins si and ti for i = 1, 2, ..., k and parity of length of the path pi is li, i.e, if li = 0, then length of pi is even, and if li = 1, then length of pi is odd for i = 1, 2, ..., k. in addition, each vertex is on at most two of these paths. we present an o(m&alpha;(m, n) log n) algorithm for fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function &alpha;(m, n) is the inverse of the ackermann function (see by tarjan [43]). this is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by kleinberg [23] and kawarabayashi and reed [20], respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement. as with the robertson-seymour algorithm to solve the k disjoint paths problem, in each iteration, we would like to either use a huge clique minor as a "crossbar", or exploit the structure of graphs in which we cannot find such a minor. here, however, we must maintain the parity of the paths and can only use an "odd clique minor". we must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. we also have algorithms running in o(m(1 + &epsilon;)) time for any &epsilon; > 0 for this problem, if k is up to o(log log log n) for general graphs, up to o(log log n) for planar graphs, and up to o(log log n/g) for graphs on the surface, where g is euler genus. furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case.
persistent homology for kernels, images, and cokernels. motivated by the measurement of local homology and of functions on noisy domains, we extend the notion of persistent homology to sequences of kernels, images, and cokernels of maps induced by inclusions in a filtration of pairs of spaces. specifically, we note that persistence in this context is well defined, we prove that the persistence diagrams are stable, and we explain how to compute them.
asymptotically optimal frugal colouring. we prove that every graph with maximum degree @d can be properly (@d+1)-coloured so that no colour appears more than o(log@d/loglog@d) times in the neighbourhood of any vertex. this is best possible up to the constant multiple in the o(-) term.
string hashing for linear probing. linear probing is one of the most popular implementations of dynamic hash tables storing all keys in a single array. when we get a key, we first hash it to a location. next we probe consecutive locations until the key or an empty location is found. at stoc'07, pagh et al. presented data sets where the standard implementation of 2-universal hashing leads to an expected number of &omega;(log n) probes. they also showed that with 5-universal hashing, the expected number of probes is constant. unfortunately, we do not have 5-universal hashing for, say, variable length strings. when we want to do such complex hashing from a complex domain, the generic standard solution is that we first do collision free hashing (w.h.p.) into a simpler intermediate domain, and second do the complicated hash function on this intermediate domain. our contribution is that for an expected constant number of linear probes, it is suffices that each key has o(1) expected collisions with the first hash function, as long as the second hash function is 5-universal. this means that the intermediate domain can be n times smaller, and such a smaller intermediate domain typically means that the overall hash function can be made simpler and at least twice as fast. the same doubling of hashing speed for o(1) expected probes follows for most domains bigger than 32-bit integers, e.g., 64-bit integers and fixed length strings. in addition, we study how the overhead from linear probing diminishes as the array gets larger, and what happens if strings are stored directly as intervals of the array. these cases were not considered by pagh et al.
an improved approximation algorithm for the column subset selection problem. we consider the problem of selecting the "best" subset of exactly k columns from an m x n matrix a. in particular, we present and analyze a novel two-stage algorithm that runs in o(min{mn2, m2n}) time and returns as output an m x k matrix c consisting of exactly k columns of a. in the first stage (the randomized stage), the algorithm randomly selects o(k log k) columns according to a judiciously-chosen probability distribution that depends on information in the top-k right singular subspace of a. in the second stage (the deterministic stage), the algorithm applies a deterministic column-selection procedure to select and return exactly k columns from the set of columns selected in the first stage. let c be the m x k matrix containing those k columns, let pc denote the projection matrix onto the span of those columns, and let ak denote the "best" rank-k approximation to the matrix a as computed with the singular value decomposition. then, we prove that [equation] with probability at least 0.7. this spectral norm bound improves upon the best previously-existing result (of gu and eisenstat [21]) for the spectral norm version of this column subset selection problem. we also prove that [equation] with the same probability. this frobenius norm bound is only a factor of &radic;k log k worse than the best previously existing existential result and is roughly o(&radic;k!) better than the best previous algorithmic result (both of deshpande et al. [11]) for the frobenius norm version of this column subset selection problem.
high rate fingerprinting codes and the fingerprinting capacity. including a unique code in each copy of a distributed document is an effective way of fighting intellectual piracy. codes designed for this purpose that are secure against collusion attacks are called fingerprinting codes. in this paper we consider fingerprinting with the marking assumption and design codes that achieve much higher rates than previous constructions. we conjecture that these codes attain the maximum possible rate (the fingerprinting capacity) for any fixed number of pirates. we prove new upper bounds for the fingerprinting capacity that are not far from the rate of our codes. on the downside the accusation algorithm of our codes are much slower than those of earlier codes. we introduce the novel model of weak fingerprinting codes where one pirate should be caught only if the identity of all other pirates are revealed. we construct fingerprinting codes in this model with improved rates but our upper bound on the rate still applies. in fact, these improved codes achieve the fingerprinting capacity of the weak model by a recent upper bound. using analytic techniques we compare the rates of our codes in the standard model and the rates of the optimal codes in the weak model. to our surprise these rates asymptotically agree, that is, their ratio tends to 1 as t goes to infinity. although we cannot prove that each one of our codes in the standard model achieves the fingerprinting capacity, this proves that asymptotically they do.