waashk/dblp huggingface dataset:
collusion-resistant mechanisms for single-parameter agents. we consider the problem of designing mechanisms with the incentive property that no coalition of agents can engage in a collusive strategy that results in an increase in the combined utility of the coalition. for single parameter agents, we give a characterization that essentially restricts such mechanisms to those that post a "take it or leave it" price to for each agent in advance. we then consider relaxing the incentive property to only hold with high probability. in this relaxed model, we are able to design approximate profit maximizing auctions and approximately efficient auctions. we generalized these results to give a methodology for designing collusion resistant mechanisms for single parameter agents. in addition, we give several results for a weaker incentive property from the literature known as group strategyproofness.
competitive auctions and digital goods. we study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. we focus on auctions that are truthful and competitive. truthful auctions encourage bidders to bid their utility; competitive auctions yield revenue within a constant factor of the revenue for optimal fixed pricing. we show that for any truthful auction, even a multi-price auction, the expected revenue does not exceed that for optimal fixed pricing. we also give a bound on how far the revenue for optimal fixed pricing can be from the total market utility. we show that several randomized auctions are truthful and competitive under certain assumptions, and that no truthful deterministic auction is competitive. we present simulation results which confirm that our auctions compare favorably to fixed pricing. some of our results extend to bounded supply markets, for which we also get truthful and competitive auctions.
randomly sampling molecules. we give the first polynomial-time algorithm for the following problem: given a degree sequence in which each degree is bounded from above by a constant, select, uniformly at random, an unlabelled connected multigraph with the given degree sequence. we also give the first polynomial-time algorithm for the following related problem: given a molecular formula, select, uniformly at random, a structural isomer having the giver formula.
better approximation guarantees for job-shop scheduling. job-shop scheduling is a classical np-hard problem. shmoys, stein, and wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation guarantee. we improve the approximation guarantee of their work and present further improvements for some important np-hard special cases of this problem (e.g., in the preemptive case where machines can suspend work on operations and later resume). we also present nc algorithms with improved approximation guarantees for some np-hard special cases.
the wake up and report problem is time-equivalent to the firing squad synchronization problem. we consider several problems relating to strongly-connected directed networks of identical finite-state processors that work synchronously in discrete time steps. the conceptually simplest of these problems is the wake up and report problem; this is the problem of having a unique "root" processor send a signal to all other processors in the network and then enter a special "done" state only when all other processors have received the signal. the most difficult of the problems we consider is the classic firing squad synchronization problem; this is the much-studied problem of achieving macro-synchrorization in a network given micro-synchronization. we show via a complex algorithmic application of the "snake" data stucture first introduced in even, litman, and winkler[6] that these two problems in particular are asymptotically time-equivalent up to a constant factor. this result leads immediately to the inclusion of several other related problems into this new asymptotic time-class.
patience is a virtue: the effect of slack on competitiveness for admission control. we consider the online competitiveness for scheduling a single resource non-preemptively in order to maximize its utilization. our work examines this model when parameterizing an instance by a new value which we term the patience. this parameter measures each job's willingness to endure a delay before starting, relative to this same job's processing time. specifically, the slack of a job is defined as the gap between its release time and the last possible time at which it may be started while still meeting its deadline. we say that a problem instance has patience κ, if each job with length ||j|| has a slack of at least κ ċ ||j||.without any restrictions placed on the job characteristics, previous lower bounds show that no algorithm, deterministic or randomized, can guarantee a constant bound on the competitiveness of a resulting schedule. previous researchers have analyzed a problem instance by parameterizing based on the ratio between the longest job's processing time and the shortest job's processing time. our main contribution is to provide a fine-grained analysis of the problem when simultaneously parameterized by patience and the range of job lengths. we are able to give tight or almost tight bounds on the deterministic competitiveness for all parameter combinations.if viewing the analysis of each parameter individually, our evidence suggests that parameterizing solely on patience provides a richer analysis than parameterizing solely on the ratio of the job lengths. for example, in the special case where all jobs have the same length, we generalize a previous bound of 2 for the deterministic competitiveness with arbitrary slacks, showing that the competitiveness for any κ ≥ 0 is exactly 1 + 1/(⌊κ⌋ + 1). without any bound on the job lengths, a simple greedy algorithm is (2+ 1/κ)- competitive for any κ > 0. more generally we will find that for any fixed ratio of job lengths, the competitiveness of the problem tends towards 1 as the patience is increased. the converse is not true, as for any fixed κ > 0 we find that the competitiveness is bounded away from 1, no matter what further restrictions are placed on the ratio of job lengths.
algorithms for infinite huffman-codes. optimal (minimum cost) binary prefix-free codes for infinite sources with geometrically distributed frequencies, e.g., p = {pi(1 - p)}&infin;i=0 0 < p < 1, were first (implicitly) suggested by golomb over thirty years ago in the context of run-length encodings. ten years later gallager and van voorhis exhibited such optimal codes for all values of p: just recently merhav, seroussi and weinberger extended this further to find optimal binary prefix-free codes for two-sided geometric distributions.these codes were derived by cleverly "guessing" optimal codes for finite sources, validating these guesses by using the sibling property of huffman encoding, and then showing that the finite codes converge in a very specific sense to an optimal infinite one.in this paper we describe the first algorithmic approach to constructing optimal prefix-free infinite codes. our approach is to define an infinite weighted graph with the property that the least cost infinite path in the graph corresponds to the optimal code. we then show that even though the graph is infinite, the leastcost infinite path has a repetitive structure and that it is therefore possible to not only find this path but to find it relatively efficiently.this approach will work for even more complicated generalizations of geometric sources where solutions can't be guessed as well as in extensions of huffman-coding for which the huffman algorithm no longer works, e.g., non-uniform cost encoding alphabet characters and/or other restrictions on the codewords. we illustrate our approach by deriving an algorithm for constructing optimal prefix free codes with a geometric source for the telegraph channel. we also implement our algorithm and show what the constructed codes look like in this case.
randomized data structures for the dynamic closest-pair problem. we describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. using this data structure the closest pair of a set of n points in d-dimensional space, for any fixed d, can be found in constant time. if a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected o(log n) time and requires expected o(n) space. this method is more efficient than any deterministic algorithm for solving the problem in dimension d > 1. the data structure can be modified to run in o(log2 n) expected time per update in the algebraic computation tree model. even this version is more efficient than the best currently known deterministic algorithm for d > 2. both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.
approximating the -multicut problem. we study the k-multicut problem: given an edge-weighted undirected graph, a set of l pairs of vertices, and a target k &le; l, find the minimum cost set of edges whose removal disconnects at least k pairs. this generalizes the well known multicut problem, where k = l. we show that the k-multicut problem on trees can be approximated within a factor of 8/3 + &epsilon;, for any fixed &epsilon; > 0, and within o(log2 n log log n) on general graphs, where n is the number of vertices in the graph.for any fixed &epsilon; > 0, we also obtain a polynomial time algorithm for k-multicut on trees which returns a solution of cost at most (2 + &epsilon;) &middot; opt, that separates at least (1 - &epsilon;) &middot; k pairs, where opt is the cost of the optimal solution separating k pairs.our techniques also give a simple 2-approximation algorithm for the multicut problem on trees using total unimodularity, matching the best known algorithm [8].
approximation algorithms for data placement on parallel disks. we study an optimization problem that arises in the context of data placement in a multimedia storage system. we are given a collection of m multimedia objects (data objects) that need to be assigned to a storage system consisting of n disks d1,d2&hellip;,dn. we are also given sets u1,u2,&hellip;,um such that ui is the set of clients seeking the ith data object. each disk dj is characterized by two parameters, namely, its storage capacity cj which indicates the maximum number of data objects that may be assigned to it, and a load capacity lj which indicates the maximum number of clients that it can serve. the goal is to find a placement of data objects to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system. we study this data placement problem for two natural classes of storage systems, namely, homogeneous and uniform ratio. we show that an algorithm developed by shachnai and tamir [2000a] for data placement achieves the best possible absolute bound regarding the number of clients that can always be satisfied. we also show how to implement the algorithm so that it has a running time of o((n + m) log(n + m)). in addition, we design a polynomial-time approximation scheme, solving an open problem posed in the same paper.
rank/select operations on large alphabets: a tool for text indexing. we consider a generalization of the problem of supporting rank and select queries on binary strings. given a string of length n from an alphabet of size &sigma;, we give the first representation that supports rank and access operations in o(lg lg &sigma;) time, and select in o(1) time while using the optimal n lg &sigma; + o(n lg &sigma;) bits. the best known previous structure for this problem required o(lg &sigma;) time, for general values of &sigma;. our results immediately improve the search times of a variety of text indexing methods.
an improved approximation algorithm for the partial latin square extension problem. the problem of completing partial latin squares arises in a number of applications, including conflict-free wavelength routing in wide-area optical networks, statistical designs, and error-correcting codes. a partial latin square is an n by n array such that each cell is either empty or contains exactly one of the colors 1, ..., n, and each color occurs at most once in any row or column. in this paper, we consider the problem of finding an extension of a given partial latin square with the maximum number of colored cells. approximation algorithms for this problem were introduced by kumar, russell, and sundaram, who gave a 2-approximation algorithm for this problem that is based on a 3-dimensional assignment formulation. we introduce a packing linear programming relaxation for this problem, and show that a natural randomized rounding algorithm yields an e/(e -- 1)-approximation algorithm.
the on-line -dimensional dictionary problem. we present a new algorithm for the on-line d-dimensional dictionary problem which has many applications including the management of geometrical objects and geometrical searching. the dictionary problem consists of executing on-line any sequence of the following operations: insert(p), delete(p) and membership(p), where p is any point in d-space. we introduce a clean structure based on balanced binary search trees, which we call d-dimensional balanced binary search trees, to represent the set of points. we present algorithms for each of the above operations that take o(d + log n) time, where n is the current number of points in the set, and each insert and delete operation requires no more than a constant number of rotations. our procedures are almost identical to the ones for balanced binary search trees. the main difference is in the way we search for an element. our search strategy is based on the principle &ldquo;assume, verify and conquer&rdquo; (avc). we apply this principle as follows. to avoid multiple verifications we shall assume that some prefixes of strings match. at the end of our search we must determine whether or not these assumptions were valid. this can be done by performing one simple verification step that takes o(d) time. the elimination of multiple verifications is important because in the worst case there are &ohgr;(log n) verifications, and each could take &ohgr;(d) time.
the rainbow skip graph: a fault-tolerant constant-degree distributed data structure. we present a distributed data structure, which we call the rainbow skip graph. to our knowledge, this is the first peer-to-peer data structure that simultaneously achieves high fault-tolerance, constant-sized nodes, and fast update and query times for ordered data. it is a non-trivial adaptation of the skipnet/skip-graph structures of harvey et al. and aspnes and shah, so as to provide fault-tolerance as these structures do, but to do so using constant-sized nodes, as in the family tree structure of zatloukal and harvey. it supports successor queries on a set of n items using o(log n) messages with high probability, an improvement over the expected o(log n) messages of the family tree. our structure achieves these results by using the following new constructs:&bull; rainbow connections: parallel sets of pointers between related components of nodes, so as to achieve good connectivity between "adjacent" components, using constant-sized nodes.&bull; hydra components: highly-connected, highly fault-tolerant components of constant-sized nodes, which will contain relatively large connected subcomponents even under the failure of a constant fraction of the nodes in the component.we further augment the hydra components in the rainbow skip graph by using erasure-resilient codes to ensure that any large subcomponent of nodes in a hydra component is sufficient to reconstruct all the data stored in that component. by carefully maintaining the size of related components and hydra components to be o(log n), we are able to achieve fast times for updates and queries in the rainbow skip graph. in addition, we show how to make the communication complexity for updates and queries be worst case, at the expense of more conceptual complexity and a slight degradation in the node congestion of the data structure.
query-efficient algorithms for polynomial interpolation over composites. the problem of polynomial interpolation is to reconstruct a polynomial based on its valuations on a set of inputs i. we consider the problem over zm when m is composite. we ask the question: given i &sube; zm, how many evaluations of a polynomial at points in i are required to compute its value at every point in i? surprisingly for composite m, this number can vary exponentially between log[i] and [i] in contrast to the prime case where [i] evaluations are necessary. while this minimization problem is np-complete, we give an efficient algorithm of query complexity within a factor t of the optimum where t is the number of prime factors of m. we use our interpolation algorithm to design algorithms for zero-testing and distributional learning of polynomials over zm. in some cases, we get an exponential improvement over known algorithms in query complexity and running time. our main technical contribution is the notion of an interpolating set for i which is a subset s of i such that a polynomial which is 0 over s must be 0 at every point in i. any interpolation algorithm needs to query an interpolating set for i. our query-efficient algorithms are obtained by constructing interpolating sets whose size is close to optimal.
caching with expiration times. caching data together with expiration times beyond which the data is no longer valid is a standard method for promoting information consistency in distributed systems, including the internet and www, large databases, and mobile telecommunications. we use the framework of competitive analysis of online algorithms and study page eviction strategies in the case where data has expiration times. we show that suitable adaptations of lru and its generalizations, namely marking algorithms, are asymptotically optimal and, in the worst case, within a multiplicative factor 2 of the lower bounds. a key technical ingredient of our analysis is a covering invariant that captures some of the subtleties introduced by expiration times. the additional difficulty of dealing with expiration times is also reflected in our analysis of the randomized online marking algorithm, as well as the offline version of the problem for which we obtain a factor 3 approximation. we complement our theoretical findings with experiments on real and synthetic data.
rounds vs queries trade-off in noisy computation. we show that a noisy parallel decision tree making o(n) queries needs &omega;(log* n) rounds to compute or of n bits. this answers a question of newman [21]. we prove more general trade-offs between the number of queries and rounds. we also completely settle a similar question for computing max in the noisy comparison tree model; these results bring out interesting differences among the noise models.
light spanners and approximate tsp in weighted graphs with forbidden minors. given an edge weighted graph g with n vertices and no k&tau;-minor and a small positive constant &epsilon;, we show that a simple greedy algorithm [1] finds a spanning subgraph approximating all shortest-path distances within a factor of 1 + &epsilon;, and with total edge weight at most o((&tau;&radic;log&tau; &middot; logn)/&epsilon;) times the weight of a minimum spanning tree. this result implies a quasi-polynomial time approximation scheme (qptas) for the traveling salesman problem (tsp) in such graphs, with running time no((&tau;4&radic;log&tau;&middot;log n&middot;log log n)/&epsilon;2).our analysis shows that a graph with detour gap number [5] &omega;(&tau;&radic;log&tau; &middot; log n) has a k&tau;-minor. we also show that this dependence on n is nearly tight, by exhibiting graphs with no k6-minor (apex graphs) and detour gap number &omega;((log n)/log log n).as a step towards eliminating the log n factors the first paragraph, we propose a generalized detour gap number, now depending on &epsilon;, and we show that it remains bounded for apex graphs and some similar graph families.
constraint solving via fractional edge covers. many important combinatorial problems can be modelled as constraint satisfaction problems, hence identifying polynomial-time solvable classes of constraint satisfaction problems received a lot of attention. in this paper, we are interested in structural properties that can make the problem tractable. so far, the largest structural class that is known to be polynomial-time solvable is the class of bounded hypertree width instances introduced by gottlob et al. [20]. here we identify a new class of polynomial-time solvable instances: those having bounded fractional edge cover number.combining hypertree width and fractional edge cover number, we then introduce the notion of fractional hypertree width. we prove that constraint satisfaction problems with bounded fractional hypertree width can be solved in polynomial time (provided that a the tree decomposition is given in the input). we also prove that certain parameterized constraint satisfaction, homomorphism, and embedding problems are fixed-parameter tractable on instances having bounded fractional hypertree width.
high-order entropy-compressed text indexes. we present a novel implementation of compressed suffix arrays exhibiting new tradeoffs between search time and space occupancy for a given text (or sequence) of n symbols over an alphabet &sigma;, where each symbol is encoded by lg&verbar;&sigma;&verbar; bits. we show that compressed suffix arrays use just nhh + &sigma; bits, while retaining full text indexing functionalities, such as searching any pattern sequence of length m in o(m lg &verbar;&sigma;&verbar; + polylog(n)) time. the term hh &le; lg &verbar;&sigma;&verbar; denotes the hth-order empirical entropy of the text, which means that our index is nearly optimal in space apart from lower-order terms, achieving asymptotically the empirical entropy of the text (with a multiplicative constant 1). if the text is highly compressible so that hn = o(1) and the alphabet size is small, we obtain a text index with o(m) search time that requires only o(n) bits. further results and tradeoffs are reported in the paper.
when indexing equals compression: experiments with compressing suffix arrays and applications. we report on a new and improved version of high-order entropy-compressed suffix arrays, which has theoretical performance guarantees similar to those in our earlier work [16], yet represents an improvement in practice. our experiments indicate that the resulting text index offers state-of-the-art compression. in particular, we require roughly 20% of the original text size---without requiring a separate instance of the text---and support fast and powerful searches. to our knowledge, this is the best known method in terms of space for fast searching.
approximate distance oracles for geometric graphs. given a geometric t-spanner graph g in ed with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. then, after o(m+n log n) preprocessing, we present an approximation scheme to answer (1+&epsilon;)-approximate shortest path queries in o(1) time. the data structure uses o(n log n) space.