waashk/dblp huggingface dataset:
sequential cavity method for computing limits of the log-partition function for lattice models. one of the key computational problems in combinatorics/statistical physics is the problem of computing limits of the log-partition functions for various statistical mechanics models on lattices. in combinatorics this limit corresponds to the exponent of various arrangements on lattices, for example the exponents of the number of independent sets, proper colorings or matchings on a lattice. in statistical physics this limit is called free energy. we propose a new method, sequential cavity, which beats the best known existing methods, such as transfer matrix method, in obtaining sharper bounds on the limits of the log-partition function for two models: independent sets (hard-core) and matchings (monomer-dimer). our method is based on a surprisingly simple representation of the log-partition function limit in terms of a certain marginal probability of a suitably modified lattice, and using recent deterministic approximation counting algorithms for these two models. our method also has a provably better theoretical performance compared with the transfer matrix method.
on the maximum quadratic assignment problem. quadratic assignment is a basic problem in combinatorial optimization that generalizes several other problems such as traveling salesman, linear arrangement, dense k subgraph, and clustering with given sizes. the input to the quadratic assignment problem consists of two n × n symmetric nonnegative matrices <inline-formula><tex-math>$w=(w_{i, j})$</tex-math></inline-formula> and <inline-formula><tex-math>$d=(d_{i, j})$</tex-math></inline-formula>. given matrices w, d, and a permutation <inline-formula><tex-math>$\pi: [n] \rightarrow [n]$</tex-math></inline-formula>, the objective function is <inline-formula><tex-math>$q(\pi):= \sum_{i, j \in [n], i \ne j} w_{i, j} \cdot d_{\pi(i), \pi(j)}$</tex-math></inline-formula>. in this paper, we study the maximum quadratic assignment problem, where the goal is to find a permutation π that maximizes <inline-formula><tex-math>$q(\pi)$</tex-math></inline-formula>. we give an <inline-formula><tex-math>$\tilde{o}(\sqrt{n})$</tex-math></inline-formula>-approximation algorithm, which is the first nontrivial approximation guarantee for this problem. the above guarantee also holds when the matrices w, d are asymmetric. an indication of the hardness of maximum quadratic assignment is that it contains as a special case the dense k subgraph problem, for which the best-known approximation ratio is <inline-formula><tex-math>$\approx n^{1/3}$</tex-math></inline-formula> (feige et al. [feige, u., g. kortsarz, d. peleg. 2001. the dense k-subgraph problem. algorithmica29(3) 410--421]). when one of the matrices w, d satisfies triangle inequality, we obtain a <inline-formula><tex-math>$2e/(e-1) \approx 3.16$</tex-math></inline-formula>-approximation algorithm. this improves over the previously best-known approximation guarantee of four (arkin et al. [arkin, e. m., r. hassin, m. sviridenko. 2001. approximating the maximum quadratic assignment problem. inform. processing lett.77 13--16]) for this special case of maximum quadratic assignment. the performance guarantee for maximum quadratic assignment with triangle inequality can be proved relative to an optimal solution of a natural linear programming relaxation that has been used earlier in branch-and-bound approaches (see, eg., adams and johnson [adams, w. p., t. a. johnson. 1994. improved linear programming-based lower bounds for the quadratic assignment problem. dimacs ser. discrete math. theoret. comput. sci.16 43--77]). it can also be shown that this linear program (lp) has an integrality gap of <inline-formula><tex-math>$\tilde{\omega}(\sqrt{n})$</tex-math></inline-formula> for general maximum quadratic assignment.
column subset selection, matrix factorization, and eigenvalue optimization. given a fixed matrix, the problem of column subset selection requests a column submatrix that has favorable spectral properties. most research from the algorithms and numerical linear algebra communities focuses on a variant called rank-revealing qr, which seeks a well-conditioned collection of columns that spans the (numerical) range of the matrix. the functional analysis literature contains another strand of work on column selection whose algorithmic implications have not been explored. in particular, a celebrated result of bourgain and tzafriri demonstrates that each matrix with normalized columns contains a large column submatrix that is exceptionally well conditioned. unfortunately, standard proofs of this result cannot be regarded as algorithmic. this paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by bourgain and tzafriri. the method involves random sampling of columns, followed by a matrix factorization that exposes the well-conditioned subset of columns. this factorization, which is due to grothendieck, is regarded as a central tool in modern functional analysis. the primary novelty in this work is an algorithm, based on eigenvalue minimization, for constructing the grothendieck factorization. these ideas also result in an approximation algorithm for the (&infin;, 1) norm of a matrix, which is generally np-hard to compute exactly. as an added bonus, this work reveals a surprising connection between matrix factorization and the famous maxcut semidefinite program.
cell probe lower bounds for succinct data structures. in this paper, we consider several static data structure problems in the deterministic cell probe model. we develop a new technique for proving lower bounds for succinct data structures, where the redundancy in the storage can be small compared to the information-theoretic minimum. in fact, we succeed in matching (up to constant factors) the lower order terms of the existing data structures with the lower order terms provided by our lower bound. using this technique, we obtain (i) the first lower bound for the problem of searching and retrieval of a substring in text; (ii) a cell probe lower bound for the problem of representing permutation &pi; with queries &pi;(i) and &pi;&minus;1(i) that matches the lower order term of the existing data structures, and (iii) a lower bound for representing binary matrices that is also matches upper bounds for some set of parameters. the nature of all these problems is that we are to implement two operations that are in a reciprocal relation to each other (search and retrieval, computing forward and inverse element, operations on rows and columns of a matrix). as far as we know, this paper is the first to provide an insight into such problems.
on low dimensional local embeddings. we study the problem of embedding metric spaces into low dimensional lp spaces while faithfully preserving distances from each point to its k nearest neighbors. we show that any metric space can be embedded into [equation] with k-local distortion of o ((log k)/p). we also show that any ultrametric can be embedded into [equation] with k-local distortion 1 + &epsilon;. our embedding results have immediate applications to local distance oracles. we show how to preprocess a graph in polynomial time to obtain a data structure of o(nk1/t log2 k) bits, such that distance queries from any node to its k nearest neighbors can be answered with stretch o(t).
maximizing submodular set functions subject to multiple linear constraints. the concept of submodularity plays a vital role in combinatorial optimization. in particular, many important optimization problems can be cast as submodular maximization problems, including maximum coverage, maximum facility location and max cut in directed/undirected graphs. in this paper we present the first known approximation algorithms for the problem of maximizing a nondecreasing submodular set function subject to multiple linear constraints. given a d-dimensional budget vector [equation], for some d &ge; 1, and an oracle for a non-decreasing submodular set function f over a universe u, where each element e &isin; u is associated with a d-dimensional cost vector, we seek a subset of elements s &sube; u whose total cost is at most [equation], such that f(s) is maximized. we develop a framework for maximizing submodular functions subject to d linear constraints that yields a (1 - &epsilon;)(1 - e&minus;1)-approximation to the optimum for any &epsilon; > 0, where d > 1 is some constant. our study is motivated by a variant of the classical maximum coverage problem that we call maximum coverage with multiple packing constraints. we use our framework to obtain the same approximation ratio for this problem. to the best of our knowledge, this is the first time the theoretical bound of 1 - e&minus;1 is (almost) matched for both of these problems.
inserting a vertex into a planar graph. we consider the problem of computing a crossing minimum drawing of a given planar graph g = (v, e) augmented by a star, i.e., an additional vertex v together with its incident edges ev = {(v, u) | u &isin; v}, in which all crossings involve ev. alternatively, the problem can be stated as finding a planar embedding of g, in which the given star can be inserted requiring the minimum number of crossings. this is a generalization of the crossing minimum edge insertion problem [15], and can help to find improved approximations for the crossing minimization problem. indeed, in practice, the algorithm for the crossing minimum edge insertion problem turned out to be the key for obtaining the currently strongest approximate solutions for the crossing number of general graphs. the generalization considered here can lead to even better solutions for the crossing minimization problem. furthermore, it offers new insight into the crossing number problem for almost-planar and apex graphs. it has been an open problem whether the star insertion problem is polynomially solvable. we give an affirmative answer by describing the first efficient algorithm for this problem. this algorithm uses the spqr-tree data structure to handle the exponential number of possible embeddings, in conjunction with dynamic programming schemes for which we introduce partitioning cost subproblems.
coresets and approximate clustering for bregman divergences. we study the generalized k-median problem with respect to a bregman divergence d&phi;. given a finite set p &sube; rd of size n, our goal is to find a set c of size k such that the sum of errors cost(p, c) = &sigma;p&epsilon;p minc&epsilon;c {d&phi;(p, c)} is minimized. the bregman k-median problem plays an important role in many applications, e.g. information theory, statistics, text classification, and speech processing. we give the first coreset construction for this problem for a large subclass of bregman divergences, including important dissimilarity measures such as the kullback-leibler divergence and the itakura-saito divergence. using these coresets, we give a (1 + &epsilon;)-approximation algorithm for the bregman k-median problem with running time o (dkn + d22(k/c)thetas;(1) logk+2n). this result improves over the previousely fastest known (1 + &epsilon;)-approximation algorithm from [1]. unlike the analysis of most coreset constructions our analysis does not rely on the construction of &epsilon;-nets. instead, we prove our results by purely combinatorial means.
a simpler implementation and analysis of chazelle's soft heaps. chazelle (jacm 47(6), 2000) devised an approximate meldable priority queue data structure, called soft heaps, and used it to obtain the fastest known deterministic comparison-based algorithm for computing minimum spanning trees, as well as some new algorithms for selection and approximate sorting problems. if n elements are inserted into a collection of soft heaps, then up to &epsilon;n of the elements still contained in these heaps, for a given error parameter &epsilon;, may be corrupted, i.e., have their keys artificially increased. in exchange for allowing these corruptions, each soft heap operation is performed in o(log 1/&epsilon;) amortized time. chazelle's soft heaps are derived from the binomial heaps data structure in which each priority queue is composed of a collection of binomial trees. we describe a simpler and more direct implementation of soft heaps in which each priority queue is composed of a collection of standard binary trees. our implementation has the advantage that no clean-up operations similar to the ones used in chazelle's implementation are required. we also present a concise and unified potential-based amortized analysis of the new implementation.
algorithms for finding an induced cycle in planar graphs and bounded genus graphs. in this paper, we consider the problem of finding an induced cycle passing through k given vertices, which we call the induced cycle problem. the significance of finding induced cycles stems from the fact that precise characterization of perfect graphs would require structures of graphs without an odd induced cycle, and its complement. there has been huge progress in the recent years, especially, the strong perfect graph conjecture was solved in [6]. concerning recognition of perfect graphs, there had been a long-standing open problem for detecting an odd hole and its complement, and finally this was solved in [4]. unfortunately, the problem of finding an induced cycle passing through two given vertices is np-complete in a general graph [2]. however, if the input graph is constrained to be planar and k is fixed, then the induced cycle problem can be solved in polynomial time [13, 14, 16]. in particular, an o(n2) time algorithm is given for the case k = 2 by mcdiarmid, reed, schrijver and shepherd [18], where n is the number of vertices of the input graph. our main results in this paper are to improve their result in the following sense. 1. the number of vertices k is allowed to be non-trivially super constant number, up to k = o((log n/log log n)2/3). more precisely, when k = o((log n/log log n)2/3), then the icp in planar graphs can be solved in o(n2+&epsilon;) time for any &epsilon;>0. 2. the time complexity is linear if the given graph is planar and k is fixed. 3. the above results are extended to graphs embedded in a fixed surface. we note that the linear time algorithm (the second result) is independent from the first result. let us point out that we give the first polynomial time algorithm for the problem for the bounded genus case. in fact, our proof gives a short proof of a result announced in [20] (without complete proof) which gives a linear time algorithm for the disjoint paths problem for fixed k for the bounded genus case. we also extend this result to the induced disjoint paths problem. let us observe that if k is as a part of the input, then the problem is still np-complete, and so we need to impose some condition on k.
scalably scheduling processes with arbitrary speedup curves. we give a scalable ((1+&epsilon;)-speed o(1)-competitive) non-clairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time.
on smoothed -cnf formulas and the walksat algorithm. in this paper we study the model of &epsilon;-smoothed k-cnf formulas. starting from an arbitrary instance f with n variables and m = dn clauses, apply the &epsilon;-smoothing operation of flipping the polarity of every literal in every clause independently at random with probability &epsilon;. keeping &epsilon; and k fixed, and letting the density d = m/n grow, it is rather easy to see that for d &ge; &epsilon;-k ln 2, f becomes whp unsatisfiable after smoothing. we show that a lower density that behaves roughly like &epsilon;-k+1 suffices for this purpose. we also show that our bound on d is nearly best possible in the sense that there are k-cnf formulas f of slightly lower density that whp remain satisfiable after smoothing. one consequence of our proof is a new lower bound of &omega;(2k/k2) on the density up to which walksat solves random k-cnfs in polynomial time whp. we are not aware of any previous rigorous analysis showing that walksat is successful at densities that are increasing as a function of k.
finding shortest contractible and shortest separating cycles in embedded graphs. we give a polynomial-time algorithm to find a shortest contractible cycle (i.e., a closed walk without repeated vertices) in a graph embedded in a surface. this answers a question posed by hutchinson. in contrast, we show that finding a shortest contractible cycle through a given vertex is np-hard. we also show that finding a shortest separating cycle in an embedded graph is np-hard. this answers a question posed by mohar and thomassen.
probability, algorithms and complexity. the talk will be a little sightseeing tour through some areas of mathematics and theoretical computer science that i found and find fascinating the tour may touch on the development of a gamblers fortune, the multiplication of numbers and of matrices, probabilistic tests of primality and the complexity of continued fractions.
a new approach to incremental topological ordering. let g = (v, e) be a directed acyclic graph (dag) with n = |v| and m = |e|. we say that a total ordering &pr; on vertices v is a topological ordering if for every edge (u, v) &isin; e, we have u &isin; v. in this paper, we consider the problem of maintaining a topological ordering subject to dynamic changes to the underlying graph. that is, we begin with an empty graph g = (v, &oslash;) consisting of n nodes. the adversary adds m edges to the graph g, one edge at a time. throughout this process, we maintain an online topological ordering of the graph g. in this paper, we present a new algorithm that has a total cost of o(n2logn) for maintaining the topological ordering throughout all the edge additions. at the heart of our algorithm is a new approach for maintaining the ordering. instead of attempting to place the nodes in an ordered list, we assign each node a label that is consistent with the ordering, and yet can be updated efficiently as edges are inserted. when the graph is dense, our algorithm is more efficient than existing algorithms. by way of contrast, the best known prior algorithms achieve only o(min(m1.5, n2.5)) cost.
from coding theory to efficient pattern matching. we consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. given a text t of length n and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the alignments for which the pattern matches the text with hamming distance at most k and also returns the location and identity of each mismatch. the algorithm we present is deterministic and runs in &otilde;(kn) time, matching the best known randomised time complexity to within logarithmic factors. the solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.
collecting weighted items from a dynamic queue. we consider the problem of collecting weighted items from a dynamic queue s. before each step, some items at the front of s can be deleted and some other items can be added to s at any place. an item, once deleted, cannot be re-inserted --- in other words, it "expires". we are allowed to collect one item from s per step. each item can be collected only once. the objective is to maximize the total weight of the collected items. we study the online version of the dynamic queue problem. it is quite easy to see that the greedy algorithm that always collects the maximum-value item is 2-competitive, and that no deterministic online algorithm can be better than 1.618-competitive. we improve both bounds: we give a 1.89-competitive algorithm for general dynamic queues and we show a lower bound of 1.632 on the competitive ratio. we also provide other upper and lower bounds for restricted versions of this problem. the dynamic queue problem is a generalization of the well-studied buffer management problem, and it is an abstraction of the buffer management problem for network links with intermittent access.
dimension detection via slivers. we present a novel approach to estimate the dimension m of an unknown manifold m &sub; rd with positive reach from a set of point samples p &sub; m. it works by analyzing the shape of simplices formed by point samples. suppose that p is drawn from m according to a poisson process with an unknown parameter &lambda;. let k be some fixed positive integer. when &lambda; is large enough, we prove that the dimension can be correctly output in o(kd|p|1+1/k) time with probability greater than 1-2-k. we experimented with a practical variant and showed that its performance is competitive with several previous methods.
approximating fractional hypertree width. fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. its algorithmic importance comes from the fact that, as shown in previous work, constraint satisfaction problems (csp) and various problems in database theory are polynomial-time solvable if the input contains a bounded-width fractional hypertree decomposition of the hypergraph of the constraints. in this article, we show that for every fixed w &ge; 1, there is a polynomial-time algorithm that, given a hypergraph h with fractional hypertree width at most w, computes a fractional hypertree decomposition of width o(w3) for h. this means that polynomial-time algorithms relying on bounded-width fractional hypertree decompositions no longer need to be given a decomposition explicitly in the input, since an appropriate decomposition can be computed in polynomial time. therefore, if h is a class of hypergraphs with bounded fractional hypertree width, then a csp restricted to instances whose structure is in h is polynomial-time solvable. this makes bounded fractional hypertree width the most general known hypergraph property that makes csp, boolean conjunctive queries, and conjunctive query containment polynomial-time solvable.
the ratio index for budgeted learning, with applications. in the budgeted learning problem, we are allowed to experiment on a set of alternatives (given a fixed experimentation budget) with the goal of picking a single alternative with the largest possible expected payoff. constant factor approximation algorithms for this problem were developed by guha and munagala by rounding a linear program that couples the various alternatives together. in this paper we present an index for this problem, which we call the ratio index, which also guarantees a constant factor approximation. index-based policies have the advantage that a single number (i.e. the index) can be computed for each alternative irrespective of all other alternatives, and the alternative with the highest index is experimented upon. this is analogous to the famous gittins index for the discounted multi-armed bandit problem. the ratio index has several interesting structural properties. first, we show that it can be computed in strongly polynomial time. second, we show that with the appropriate discount factor, the gittins index and our ratio index are constant factor approximations of each other, and hence the gittins index also gives a constant factor approximation to the budgeted learning problem. finally, we show that the ratio index can be used to create an index-based policy that achieves an o(1)-approximation for the finite horizon version of the multi-armed bandit problem. moreover, the policy does not require any knowledge of the horizon (whereas we compare its performance against an optimal strategy that is aware of the horizon). this yields the following surprising result: there is an index-based policy that achieves an o(1)-approximation for the multi-armed bandit problem, oblivious to the underlying discount factor.