waashk/dblp huggingface dataset:
improved approximation algorithms for max sat. max sat (the maximum satisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. in this paper, we consider approximation algorithms for max sat proposed by goemans and williamson and present a sharpened analysis of their performance guarantees. we also show that these algorithms, combined with recent approximation algorithms for max 2sat, max 3sat, and max sat due to feige and goemans, karloff and zwick, and zwick, respectively, lead to an improved approximation algorithm for max sat. by using the max 2sat and 3sat algorithms, we obtain a performance guarantee of 0.7846, and by using zwick's algorithm, we obtain a performance guarantee of 0.8331, which improves upon the performance guarantee of 0.7977 based on zwick's conjecture. the best previous result for max sat without assuming zwick's conjecture is a 0.770-approximation algorithm of asano. our best algorithm requires a new family of 3/4-approximation algorithms that generalize a previous algorithm of goemans and williamson.
inoculation strategies for victims of viruses and the sum-of-squares partition problem. we propose a simple game for modeling containment of the spread of viruses in a graph of n nodes. each node must choose to either install anti-virus software at some known cost c, or risk infection and a loss l if a virus that starts at a random initial point in the graph can reach it without being stopped by some intermediate node. the goal of individual nodes is to minimize their individual expected cost. we prove many game theoretic properties of the model, including an easily applied characterization of nash equilibria, culminating in our showing that allowing selfish users to choose nash equilibrium strategies is highly undesirable, because the price of anarchy is an unacceptable &theta;(n) in the worst case. this shows in particular that a centralized solution can give a much better total cost than an equilibrium solution. though it is np-hard to compute such a social optimum, we show that the problem can be reduced to a previously unconsidered combinatorial problem that we call the sum-of-squares partition problem. using a greedy algorithm based on sparse cuts, we show that this problem can be approximated to within a factor of o(log2 n), giving the same approximation ratio for the inoculation game.
towards understanding the predictability of stock markets from the perspective of computational complexity. this paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. we develop a simple agent-based model for a stock market where the agents are traders equipped with simple trading strategies, and their trades together determine the stock prices. computer simulations show that a basic case of this model is already capable of generating price graphs which are visually similar to the recent price movements of high tech stocks. in the general model, we prove that if there are a large number of traders but they employ a relatively small number of strategies, then there is a polynomial-time algorithm for predicting future price movements with high accuracy. on the other hand, if the number of strategies is large, market prediction becomes complete in two new computational complexity classes cpp and bcpp, where pnp[&ogr;(log n)] e bcpp e cpp = pp. these computational completeness results open up a novel possibility that the price graph of a actual stock could be sufficiently deterministic for various prediction goals but appear random to all polynomial-time prediction algorithms.
skip graphs. skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where elements are stored in separate nodes that may fail at any time. they are designed for use in searching peer-to-peer networks, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. in addition, constructing, inserting new elements into, searching a skip graph and detecting and repairing errors in the data structure introduced by node failures can be done using simple and straight-forward algorithms.
dotted interval graphs and high throughput genotyping. we introduce a generalization of interval graphs, which we call dotted interval graphs (dig). a dotted interval graph is an intersection graph of arithmetic progressions (=dotted intervals). coloring of dotted intervals graphs naturally arises in the context of high throughput genotyping. we study the properties of dotted interval graphs, with a focus on coloring. we show that any graph is a dig but that digd graphs, i.e. digs in which the arithmetic progressions have a jump of at most d, form a strict hierarchy. we show that coloring digd, graphs is np-complete even for d = 2. for any fixed d, we provide a 7/8d approximation for the coloring of digd graphs.
on-line generalized steiner problem. the generalized steiner problem (gsp) is defined as follows. we are given a graph with non-negative edge weights and a set of pairs of vertices. the algorithm has to construct minimum weight subgraph such that the two nodes of each pair are connected by a path.off-line gsp approximation algorithms were given in agarwal et al. (siam j. comput. 24(3) (1995) 440) and goemans and williamson (siam j. comput. 24(2) (1995) 296). we consider the on-line gsp, in which pairs of vertices arrive on-line and are needed to be connected immediately.we show that the online min-cost (i.e. greedy) strategy for this problem has o(log2 n) competitive ratio. the previous best algorithm was o(√nlog n) competitive (workshop on algorithms and data structures, 1993, pp. 622-633). following this work a different (non-greedy) algorithm has been shown to achieve an o(log n) competitive ratio (proceedings of the 29th acm symposium on theory of computing, 1997, pp. 344-353).we also consider the network connectivity leasing problem which is a generalization of the gsp. here, edges of the graph can be either bought or leased for different costs. we provide simple randomized algorithm based on on-line generalized steiner algorithms whose competitive ratio is within a constant factor of the best competitive algorithm for the on-line gsp.
online client-server load balancing without global information. we consider distributed online algorithms for maximizing through-put in a network of clients and servers, modeled as a bipartite graph. unlike most prior work on online load balancing, we do not assume centralized control and seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. our problem can be seen as analogous to the recent work on oblivious routing in [8, 14, 19], but with the objective of maximizing through-put rather than minimizing congestion. in contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm. this is accompanied by simple algorithms achieving upper bounds which are tight in terms of k, the maximum throughput achievable by an omniscient algorithm. finally, we examine a restricted model in which clients, upon becoming active, must remain so for at least log(n) time steps. in contrast to the primarily negative results in the oblivious case, here we present an algorithm which is constant-competitive. our lower bounds justify the intuition, implicit in earlier work on the subject [2], that some such restriction (i.e. requiring some stability in the demand pattern over time) is necessary in order to achieve a constant --- or even polylogarithmic --- competitive ratio.
improved recommendation systems. we consider a model of competitive recommendation systems proposed by drineas et al. [4]. in recommendation systems (e.g., for books or movies), the system tracks which product each user chose in the past, and tries to deduce which other products an asking user is likely to be satisfied with. obviously, recommendation systems can be effective only for users who share preferences with many other users. such users are said to belong to a "dominant type." current approaches to on-line recommendation systems involve using singular value decomposition (svd), which is computationally intensive and, more important, often applicable only under additional strong conditions. specifically, correctness is guaranteed in [4] only if users of different dominant types essentially do not share a product they like ("type separability"), and only if the number of users in non-dominant types is significantly smaller than the number of users in dominant types ("gap assumption"). the complexity of that algorithm is o(mn), where m and n denote the number of users and products, respectively. in this paper, we show that in fact, very simple combinatorial algorithms can make good recommendations without using svd. our algorithms require neither the type separability nor the gap assumption, they are naturally amenable to distibuted computation, and their complexity is lower. in particular, the paper presents an o(m + n) time centralized algorithm and a distributed algorithm that can be implemented in a peer-to-peer model even in the presence of adaptively colluding malicious players, with only logarithmic over-head.
the hyperring: a low-congestion deterministic data structure for distributed environments. in this paper we study the problem of designing searchable concurrent data structures with performance guarantees that can be used in a distributed environment where data elements are stored in a dynamically changing set of nodes. searchable data structures are data structures that provide three basic operations: insert, delete, and search. in addition to searching for an exact match, we demand that for a data structure to be called "searchable", search also has to be able to search for the closest successor or predecessor of a data item. such a property has a tremendous advantage over just exact match, because it would allow to implement many data base applications.we are interested in finding a searchable concurrent data structure that has (1) a low degree, (2) requires a small amount of work for insert and delete operations, and (3) is able to handle concurrent search requests with low congestion and dilation.we present the first deterministic concurrent data structure, called hyperring, that can fulfill all of these objectives in a polylogarithmic way. in fact, the hyperring has a degree of o(log n), requires o(log3 n) work for insert and delete operations, and can handle concurrent search requests to random destinations, one request per node, with congestion and dilation o(log n) w.h.p.most of the previous solutions for distributed environments are not searchable (in our sense) but only provide exact lookup, and those that are searchable do not have proofs about the congestion caused by concurrent search requests.
the competitiveness of on-line assignments. consider the on-line problem where a number of servers are ready to provide service to a set of customers. each customer's job can be handled by any of a subset of the servers. customers arrive one-by-one and the problem is to assign each customer to an appropriate server in a manner that will balance the load on the servers. this problem can be modeled in a natural way by a bipartite graph where the vertices of one side (customers) appear one at a time and the vertices of the other side (servers) are known in advance. we derive tight bounds on the competitive ratio in both deterministic and randomized cases. let n denote the number of servers. in the deterministic case we provide an on-line algorithm that achieves a competitive ratio of k = [log2 n] (up to an additive 1) and prove that this is the best competitive ratio that can be achieved by any deterministic on-line algorithm. in a similar way we prove that the competitive ratio for the randomized case is k=ln(n) (up to an additive 1). we conclude that for this problem, randomized algorithms differ from deterministic ones by precisely a constant factor.
on the diameter of eulerian orientations of graphs. we compare the diameter of a graph with the directed diameter of its eulerian orientations. we obtain positive results under certain symmetry conditions.an eulerian orientation of a graph is an orientation such that each vertex has the same indegree and outdegree. a graph is vertex-transitive if its vertices are equivalent under automorphisms.we show that the directed diameter of an eulerian orientation of a finite vertex-transitive graph cannot be much larger than the undirected diameter; our bound on the directed diameter is o (d&delta; ln n) where d is the undirected diameter, &delta; is the (out)degree of the vertices, and n is the number of vertices. this implies that for eulerian orientations of vertex-transitive graphs-of bounded degree, the gap between the two diameters is at most quadratic.as a consequence, we are able to compare the word length and the positive word length of elements of a finite group in terms of a given set of generators; we show that the gap is at most nearly quadratic, where the term "nearly" refers to a factor, polylogarithmic in the order of the group.it follows that recent polynomial bounds on the diameter of certain large classes of cayley graphs of the symmetric group and certain linear groups automatically extend to directed cayley graphs. the result also shows that the directed and undirected versions of long standing conjectures regarding the diameter of cayley graphs of various classes of groups, including transitive permutation groups and finite simple groups, are equivalent.we also show that for edge-transitive digraphs, the directed diameter is o(d ln n).on the other hand, if we weaken the condition of vertex-transitivity to regularity (all vertices have the same degree), then the directed diameter is no longer polynomially bounded in terms of the undirected diameter and the maximum degree (and in n = o(d ln &delta;)).our upper bounds on the diameter raise the algorithmic challenge to find paths of the length guaranteed by these results. while for undirected graphs, most (but not all) relevant proofs are algorithmic, our bounds for the directed diameter are obtained via a pigeon-hole argument based on expansion and yield existence only.
deciding finiteness of matrix groups in las vegas polynomial time. let g be a group of matrices with integer entries, given by a list of generators. it is known that membership in such a group is undecidable, even for 4 x 4 integral matrices [mi]. in this paper we show that one can decide whether or not g is finite, in las vegas polynomial time. the key estimate derived makes the entire &ldquo;black box group&rdquo; theory ([bsz], [bcfls], [ba2], [bkl]) applicable to the finite groups of integral matrices. in particular it follows that in this case, structural properties such as solvability and nilpotence are decidable in monte carlo polynomial time; and membership, order, isomorphism, and a host of other problems are in the relatively low complexity class am &cap; coam [ba1]. we give two algorithms. the simpler one (monte carlo but not las vegas) employs a refinement of the random walk technique over groups, developed in [ba3] (applied here to infinite groups). the termination rule rests on a new estimate on the bit-size of the elements of finite groups g, obtained via polynomial time symbolic manipulation of representations over algebraic number fields using results of [br]. this symbolic manipulation technique is the basis of the las vegas algorithm. (a las vegas algorithm is a rnadomized algorithm which never errs; but with small probability, it may r eport failure.)
multiplicative equations over commuting matrices. we consider the solvability of the equation a_1^x_1 * ... * x_k^x_k = b and generalizations, where the a_i and b are given commuting matrices over an algebraic number field f. in the semigroup membership problem, the variables x_i are constrained to be nonnegative integers. while this problem is np-complete for variable k, we give a polynomial time algorithm if k is fixed. in the group membership problem, the matrices are assumed to be invertible, and the variables x_i may take on negative values. in this case we give a polynomial time algorithm for variable k and give an explicit description of the set of all solutions (as an affine lattice). the results generalize recent work of cai, lipton, and zalcstein [clz] where the case k=2 is solved using jordan normal forms (jnf). we achieve greater clarity simplicity, and generality by eliminating the use of jnf''s and referring to elementary concepts of the structure theory of algebras instead (notably, the radical and the local decomposition. partial solutions are combined using algorithms for (affine lattices. the special case of 1*1 matrices was recently solved by g. ge and we heavily rely on his results.
on the diameter of the symmetric group: polynomial bounds. we address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of generators of the symmetric group. the best available bound on the maximum required word length is exponential in n log n. polynomial bounds on the word length have previously been established for very special classes of generating sets only.in this paper we give a polynomial bound on the word length under the sole condition that one of the generators fix at least 67% of the domain. words of the length claimed can be found in las vegas polynomial time.the proof involves a markov chain mixing estimate which permits us, apparently for the first time, to break the "element order bottleneck."as a corollary, we obtain the following average-case result: for a 1 -- &delta; fraction of the pairs of generators for the symmetric group, the word length is polynomially bounded. it is known that for almost all pairs of generators, the word length is less than exp(&radic;n ln n(1 + o(1))).
near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. we address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of generators of the symmetric group sn this is equivalent to polynomial-time (o(nc)) mixing of the (lazy) random walk on sn where one step is multiplication by a generator or its inverse.we prove that the conjecture is true for almost all pairs of generators. specifically, our bound is &otilde;(n7). for almost all pairs of generators, words of this length representing any given permutation can be constructed in las vegas polynomial time. the best previous bound on the word length for a random pair of generators was ninn(1/2+o(1)) (babai-hetyei, 1992).we build on recent major progress by babai-beals-seress (soda, 2004), confirming the conjecture under the assumption that at least one of the generators has degree < 0.33n.the main technical contribution of the present paper is the following near-independence result for permutations. the first cycle of a permutation is the trajectory of the first element of the permutation domain. for a random permutation, the distribution of the length of the first cycle is uniform. we show that if &tau; &isin; sn is a given permutation of degree &ge; n3/4 and &sigma; &isin; sn is chosen at random, then the distributions of the length of the first cycle of &sigma; and the length of the first cycle in &sigma;&tau; are nearly independent. the ability of an essentially arbitrarily fixed permutation (&tau;) to "scramble" another permutation in this technical sense may be of independent interest and suggests new directions in the statistical theory of permutations pioneered by goncharov and erd&odblac;s-tur&aacute;n.
strong bias of group generators: an obstacle to the ``product replacement algorithm''. let g be a finite group. efficient generation of nearly uniformly distributed random elements in g, starting from a given set of generators of g, is a central problem in computational group theory. in this paper we demonstrate a weakness in the popular "product replacement algorithm," widely used for this purpose. the main results are the following. let nk(g) be the set of generating k-tuples of elements of g. consider the distribution of the first components of the k-tuples in nk(g) induced by the uniform distribution over nk(g). we show that there exist infinite sequences of gtoups g such that this distribution is very far from uniform in two different senses: (1) its variation distance from uniform is > 1 - ε and (2) there exists a short word (of length (loglog |g|)o(k)) which separates the two distributions with probability 1 - ε. the class of groups we analyze is direct powers of alternating groups. the methods used include statistical analysis of permutation groups, the theory of random walks, the aks sorting network, and a randomized simulation of monotone boolean operations by group operations, inspired by barrington's work on bounded-width branching programs. the problem is motivated by the product replacement algorithm which was introduced in [comm. algebra 23 (1995) 4931-4948] and is widely used. our results show that for certain groups the probability distribution obtained by the product replacement algorithm has a bias which can be detected by a short straight line program.
single-value combinatorial auctions and implementation in undominated strategies. in this paper we are interested in general techniques for designing mechanisms that approximately maximize the social welfare in the presence of selfish rational behavior. we demonstrate our results in the setting of combinatorial auctions (ca). our first main result is a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any algorithm to a dominant-strategy ascending mechanism. this technique works for any single value domain, in which each agent has the same value for each desired outcome, and this value is the only private information. in particular, for "single-value cas", where each player desires any one of several different bundles but has the same value for each of them, our technique converts any approximation algorithm to a dominant strategy mechanism that almost preserves the original approximation ratio. our second main result provides the first computationally efficient deterministic mechanism for the case of single-value multi-minded bidders (with private value and private desired bundles). the mechanism achieves an approximation to the social welfare which is close to the best possible in polynomial time (unless zpp=np). this mechanism is an implementation in undominated strategies, as well as an algorithmic implementation, notions that we justify and are of independent interest.
sampling from a moving window over streaming data. we introduce the problem of sampling from a moving window of recent items from a data stream and develop two algorithms for this problem. the first algorithm, "chain-sample", extends reservoir sampling to deal with the expiration of data elements from the sample. the expected memory usage of our algorithm is o(k) when maintaining a sample of size k over a window of the n most recent elements from the data stream, and with high probability the algorithm requires no more than o(k log n) memory.when the number of elements in the window is variable, as is the case when the size of the window is defined as a time duration rather than as a fixed number of data elements, the sampling problem becomes harder. our second algorithm, "priority-sample", works even when the number of elements in the window can vary dynamically over time. with high probability, the "priority-sample" algorithm uses no more than o(k log n) memory.