waashk/dblp huggingface dataset:
approximating min-sum -clustering in metric spaces. the min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same cluster. we give the first polynomial time non-trivial approximation algorithm for this problem. the algorithm provides an $\ratio$ approximation to the min-sum k-clustering problem in general metric spaces, with running time $\runtime$. the result is based on embedding of metric spaces into hierarchically separated trees. we also provide a bicriteria approximation result that provides a constant approximation factor solution with only a constant factor increase in the number of clusters. this result is obtained by modifying and drawing ideas from recently developed primal dual approximation algorithms for facility location.
new algorithms for an ancient scheduling problem we consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the makespan, the completion time of the last job. in the on-line version, as soon as job j arrrives, it must be assigned immediately to one of the m machines. we present two main results. the first is a (2&ndash;&egr;)-competitive deterministic algorithm for all m. the competitive ratio of all previous algorithms approaches 2 as m&rarr; &infin; . indeed, the problem of improving the competitive ratio for large m had been open since 1966, when the first algorithm for this problem appeared. the second result is an optimal randomized algorithm for the case m = 2. to the best of our knowledge, our 4/3-competitive algorithm is the first specifically randomized algorithm for the original, m-machine, on-line scheduling problem.
lower bounds for on-line graph problems with application to on-line circuit and optical routing. we present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems, and we apply such results to on-line virtual circuit and optical routing problems. lund and yannakakis [the approximation of maximum subgraph problems, in proceedings of the 20th international colloquium on automata, languages and programming, 1993, pp. 40-51] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any nontrivial, hereditary property pi--e.g., independent set, planar, acyclic, bipartite. we consider the on-line version of this family of problems, where some graph g is fixed and some subgraph h of g is presented on-line, vertex by vertex. the on-line algorithm must choose a subset of the vertices of h, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property pi. furthermore, we study the on-line version of graph coloring whose off-line version has also been shown to be inapproximable [c. lund and m. yannakakis, on the hardness of approximating minimization problems, in proceedings of the 25th acm symposium on theory of computing, 1993], on-line max edge-disjoint paths, and on-line path coloring problems. irrespective of the time complexity, we show an omega(nepsilon) lower bound on the competitive ratio of randomized on-line algorithms for any of these problems. as a consequence, we obtain an omega(nepsilon) lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks. similar lower bounds are obtained for on-line optical routing as well.
competitive algorithms for distributed data management (extended abstract) we deal with the competitive analysis of algorithms for managing data in a distributed environment. we deal with the file allocation problem ([c], [df], [ml]), where copies of a file may be stored in the local storage of some subset of processors, copies may be replicated and discarded over time so as to optimize communication costs, but multiple copies must be kept consistent and at least one copy must be stored somewhere in the network at all times. we deal with competitive algorithms for minimizing communication costs, over arbitrary sequences of reads and writes, and arbitrary network topologies. we define the constrained file allocation problem to be the solution of many individual file allocation problems simultaneously, subject to the constraints of local memory size. we give competitive algorithms for this prblem on uniform networks. we then introduce distributed competitive algorithms for on-line data tracking (a generalization of mobile user tracking [ap1, ap3] to transform our competitive distributed data management algorithms into distributed algorithms themselves.
on metric ramsey-type phenomena. this paper deals with ramsey-type theorems for metric spaces. such a theorem states that every n point metric space contains a large subspace which can be embedded with some fixed distortion in a metric space from some special class.our main theorem states that for any ε>0, every n point metric space contains a subspace of size at least n1-ε which is embeddable in an ultrametric with o(log(1/ε)/ε distortion. this in particular provides a bound for embedding in euclidean spaces. the bound on the distortion is tight up to the log(1/ε) factor even for embedding in arbitrary euclidean spaces. this result can be viewed as a non-linear analog of dvoretzky's theorem, a cornerstone of modern banach space theory and convex geometry.our main ramsey-type theorem and techniques naturally extend to give theorems for classes of hierarchically well-separated trees which have algorithmic implications, and can be viewed as the solution of a natural clustering problem.we further include a comprehensive study of various other aspects of the metric ramsey problem.
feasibility testing for systems of real quadratic equations we consider the problem of deciding whether a given system of quadratic homogeneous equations over the reals has non-trivial solution. we design an approximative algorithm whose complexity is polynomial in the number of variables and exponential in the number of equations. some applications to general systems of polynomial equations and inequalities over the reals are discussed.
a sublinear algorithm for weakly approximating edit distance. we show how to determine whether the edit distance between two given strings is small in sublinear time. specifically, we present a test which, given two n-character strings a and b, runs in time o(n) and with high probability returns "close" if their edit distance is o(nα), and "far" if their edit distance is ω(n), where α is a fixed parameter less than 1. our algorithm for testing the edit distance works by recursively subdividing the strings a and b into smaller substrings and looking for pairs of substrings in a, b with small edit distance. to do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. as a result, our test runs in time õ(nmax(α/2, 2α - 1\)) for any fixed α < 1. our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.we also show a lower bound of ω(nα/2) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most nα from those with edit distance at least n/6.
polynomial time algorithm for computing the top betti numbers of semi-algebraic sets defined by quadratic inequalities. for any fixed l > 0, we present an algorithm which takes as input a semi-algebraic set, s, defined by p1 ≥ 0,...,ps ≥ 0, where each pi ∈ r[x1,...,xk] has degree ≤ 2, and computes the top l betti numbers of s, bk-1(s), ..., bk-l(s), in polynomial time. the complexity of the algorithm, stated more precisely, is σi=0l+2 (si k2o((l,s)). for fixed l, the complexity of the algorithm can be expressed as sl+2 k2o(l), which is polynomial in the input parameters s and k. to our knowledge this is the first polynomial time algorithm for computing non-trivial topological invariants of semi-algebraic sets in rk defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. for fixed s, we obtain by letting l = k, an algorithm for computing all the betti numbers of s whose complexity is k2o(s)
sublinear algorithms for testing monotone and unimodal distributions. the complexity of testing properties of monotone and unimodal distributions, when given access only to samples of the distribution, is investigated. two kinds of sublinear-time algorithms---those for testing monotonicity and those that take advantage of monotonicity---are provided. the first algorithm tests if a given distribution on [n] is monotone or far away from any monotone distribution in l1-norm; this algorithm uses o(√n) samples and is shown to be nearly optimal. the next algorithm, given a joint distribution on [n] x [n], tests if it is monotone or is far away from any monotone distribution in l1-norm; this algorithm uses o(n3/2) samples. the problems of testing if two monotone distributions are close in l1-norm and if two random variables with a monotone joint distribution are close to being independent in l1-norm are also considered. algorithms for these problems that use only poly(log n) samples are presented. the closeness and independence testing algorithms for monotone distributions are significantly more efficient than the corresponding algorithms as well as the lower bounds for arbitrary distributions. some of the above results are also extended to unimodal distributions.
on classes of computable functions the complexity closure of a computable function is defined by a set of axioms. the axioms are satisfied by complexity classes that are computation time closed and also by other complexity classes which do not have this property. it is then shown that there exist honest recursive functions whose complexity closure are setwise incomparable. further that there exist chains of honest recursive functions whose complexity closures are densely ordered under set inclusion.
an analysis of the full alpha-beta pruning algorithm an analysis of the alpha-beta pruning algorithm is presented which takes into account both shallow and deep cut-offs. a formula is first developed to measure the average number of terminal nodes examined by the algorithm in a uniform free of degree n and depth d when ties are allowed among the bottom positions: specifically, all bottom values are assumed to be independent identically distributed random variables drawn from a discrete probability distribution. a worst case analysis over all possible probability distributions is then presented by considering the limiting case when the discrete probability distribution tends to a continuous probability distribution. the branching factor of the alpha-beta pruning algorithm is shown to grow with n as &thgr;(n/in n), therefore confirming a claim by knuth and moore that deep cut-offs only have a second order effect on the behavior of the algorithm.
computing the first betti number and the connected components of semi-algebraic sets. in this paper we describe the first singly exponential algorithm for computing the first betti number of a given semi-algebraic set. we also describe algorithms for obtaining semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set. singly exponential algorithms for computing the zero-th betti number, and the euler-poincaré characteristic, were known before. no singly exponential algorithm was known for computing any of the individual betti numbers other than the zero-th one.
improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. this paper presents improved algorithms for the following problem: given an unweighted directed graph g(v,e) and a sequence of on-line shortest-path/reachability queries interspersed with edge-deletions, develop a data-structure that can answer each query in optimal time, and can be updated efficiently after each edge-deletion. the central idea underlying our algorithms is a scheme for implicitly storing all-pairs reachability/shortest-path information, and an efficient way to maintain this information. our algorithms are randomized and have one-sided inverse polynomial error for query.
angles of planar triangular graphs. we give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating its angles; we also discuss minimality properties of the characterization. the characterization can be used: (1) to decide in linear time whether a given distribution of angles between the edges of a planar triangular graph can result in a planar drawing; (2) to reduce the problem of maximizing the minimum angle in a planar straight-line drawing of a planar triangular graph to a nonlinear optimization problem purely on a space of angles; (3) to give a characterization of the planar drawings of a triconnected graph through a system of equations and inequalities relating its angles; (4) to give a characterization of delaunay triangulations through a system of equations and inequalities relating its angles; (5) to give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating the lengths of its edges; in turn, this result allows us to give a new characterization of the disc-packing representations of planar triangular graphs.
a general sequential time-space tradeoff for finding unique elements an optimal &ohgr;(n2) lower bound is shown for the time-space product of any r-way branching program that determines those values which occur exactly once in a list of n integers in the range [1, r] where r &ge; n. this &ohgr;(n2) tradeoff also applies to the sorting problem and thus improves the previous time-space tradeoffs for sorting. because the r-way branching program is a such a powerful model these time-space product tradeoffs also apply to all models of sequential computation that have a fair measure of space such as off-line multi-tape turing machines and off-line log-cost rams.
the complexity of approximating entropy. (math) we consider the problem of approximating the entropy of a discrete distribution under several models. if the distribution is given explicitly as an array where the i-th location is the probability of the i-th element, then linear time is both necessary and sufficient for approximating the entropy.we consider a model in which the algorithm is given access only to independent samples from the distribution. here, we show that a &lgr;-multiplicative approximation to the entropy can be obtained in o(n(1+&eta;)/&lgr;2 < poly(log n)) time for distributions with entropy &omega;(&lgr; &eta;), where n is the size of the domain of the distribution and &eta; is an arbitrarily small positive constant. we show that one cannot get a multiplicative approximation to the entropy in general in this model. even for the class of distributions to which our upper bound applies, we obtain a lower bound of &omega;(nmax(1/(2&lgr;2), 2/(5&lgr;2&mdash;2)).we next consider a hybrid model in which both the explicit distribution as well as independent samples are available. here, significantly more efficient algorithms can be achieved: a &lgr;-multiplicative approximation to the entropy can be obtained in o(&lgr;2.finally, we consider two special families of distributions: those for which the probability of an element decreases monotonically in the label of the element, and those that are uniform over a subset of the domain. in each case, we give more efficient algorithms for approximating the entropy.
optimal bounds for decision problems on the crcw pram optimal &ohgr;(log n/log log n) lower bounds on the time for crcw prams with polynomially bounded numbers of processors or memory cells to compute parity and a number of related problems are proven. a strict time hierarchy of explicit boolean functions of n bits on such machines that holds up to &ogr;(log n/log log n) time is also exhibited. that is, for every time bound t within this range a function is exhibited that can be easily computed using polynomial resources in time t but requires more than polynomial resources to be computed in time t - 1. finally, it is shown that almost all boolean functions of n bits require log n - log log n + &ohgr;(1) time when the number of processors is at most polynomial in n. the bounds do not place restrictions on the uniformity of the algorithms nor on the instruction sets of the machines.
randomized versus nondeterministic communication complexity our main result is the demonstration of a boolean function f with nondeterministic and co-nondeterministic complexities o(log n) and &egr;-error randomized complexity &ohgr;(log2 n), for 0 &le; &egr; < 1/2. this is the first separation of this kind for a decision problem.
time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. recently, the first non-trivial time-space tradeoff lower bounds have been shown for decision problems in p, using notions derived from the study of two-party communication complexity. these results are proven directly for branching programs, natural generalizations of decision trees to directed graphs that provide elegant models of both non-uniform time t and space s simultaneously.we develop a new lower bound criterion, based on extending two-party communication complexity ideas to multiparty communication complexity. applying this criterion to an explicit boolean function based on a multilinear form overgf(2^s) for suitable s, we show lower bounds that yield t=\omega(n\log^2 n) whens\le n^{1-\epsilon}\log |d| for large input domain d. this improves the previous best lower bounds for general branching programs of t=\omega(n\log (n/s)).using these ideas, we also give a conceptually simple proof of the relationship between multiparty communication complexity and time-space tradeoffs for oblivious branching programs (previously shown by babai et al.). this relationship yields time-space tradeoff lower bounds of the form t=\omega(n\log^2(n/s)) for 1gap on oblivious branching programs. since 1gap has a trivial general branching program of time n and space o(\log n), this provides the first separation between general and oblivious branching program computation.finally, we develop lower bounds for nearest-neighbor problems involving n data points in a variety of d-dimensional metric spaces. in yao's general cell-probe model, borodin et al. showed that time \omega(d/\log n) is required for nearest-neighbor queries over \{0,1\}^d. we consider slightly more restricted data structure algorithms that are charged for access to individual components of the query.in this model, for certain d-dimensional metric spaces, we prove query time lower bounds \omega(d\log d) or \omega(d\sqrt{\log d/\log\log d}), depending on the metric. these follow using a general relationship, suggested by miltersen et al., between data structure bounds and time-space tradeoff bounds for branching programs. the above bounds use coordinates of size polynomial in d. over \{0,1\}^d, we prove query time lower bounds of \omega(d) in general and \omega(d\log d) when the data structure corresponds to an oblivious branching program.
non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in cpu scheduling in time sharing operating systems. a widely used measure for the responsiveness of the system is the average flow time of the jobs, i.e. the average time spent by jobs in the system between release and completion.the windows nt and the unix operating system scheduling policies are based on the multi-level feedback algorithm [12, 1]. in this paper we prove that a randomized version of the multi-level feedback algorithm is competitive for single and parallel machine systems, in our opinion providing one theoretical validation of the goodness of an idea that has been very effective in practice along the last two decades.the randomized multi-level feedback algorithm (rmlf) was first proposed by kalyanasundaram and pruhs [7] for a single machine achieving an o(\log n \log\log n) competitive ratio to minimize the average flow time against the on-line adaptive adversary, where n is the number of jobs that are released. we present a version of rmlf working for any numberm of parallel machines. we show for rmlf a first o(\log n\log \frac{n}{m}) competitiveness result against the oblivious adversary on parallel machines. we also show that the same rmlf algorithm surprisingly achieves a tight o(\log n) competitive ratio against the oblivious adversary on a single machine, therefore matching the lower bound of [10].
properties of acyclic database schemes there is a class of database descriptions, involving one &ldquo;acyclic&rdquo; join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. further, this class has many desirable properties. some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. it is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. this paper is intended to summarize the results that will appear in more detail in [fmu] and [bfmy].
equivalence of relational database schemes we investigate the question of when two database schemes embody the same information. we argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. when data dependencies are given, we need only consider those fixed points that satisfy the dependencies. a polynomial algorithm to test the equivalence of database schemes, when there are no dependencies, is given. we also provide an exponential algorithm to handle the case where there are functional and/or multivalued dependencies. furthermore, we give a polynomial time test to determine whether a project-join mapping preserves a set of functional dependencies, and a polynomial time algorithm for equivalence of database schemes whose project-join mappings do preserve the given set of functional dependencies. lastly, we introduce the &ldquo;update sets&rdquo; approach to database design as an application of these results.
random knapsack in expected polynomial time. we present the first average-case analysis proving a polynomial upper bound on the expected running time of an exact algorithm for the 0/1 knapsack problem. in particular, we prove for various input distributions, that the number of pareto-optimal knapsack fillings is polynomially bounded in the number of available items. an algorithm by nemhauser and ullmann can enumerate these solutions very efficiently so that a polynomial upper bound on the number of pareto-optimal solutions implies an algorithm with expected polynomial running time.the random input model underlying our analysis is quite general and not restricted to a particular input distribution. we assume adversarial weights and randomly drawn profits (or vice versa). our analysis covers general probability distributions with finite mean and, in its most general form, can even handle different probability distributions for the profits of different items. this feature enables us to study the effects of correlations between profits and weights. our analysis confirms and explains practical studies showing that so-called strongly correlated instances are harder to solve than weakly correlated ones.