waashk/dblp huggingface dataset:
average-case analysis of some plurality algorithms. given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. we focus on the expected number of color comparisons when the cn colorings are equally probable. we analyze an obvious algorithm, showing that its expected performance is c2 + c &minus; 2/2c n &minus; o(c2), with variance &theta;(c2n). we present and analyze an algorithm for the case c &equals; 3 colors whose average complexity on the 3n equally probable inputs is 7083/5425n + o(&sqrt;n) &equals; 1.3056&hellip;n + o(&sqrt; n), substantially better than the expected complexity 5/3n + o(1) &equals; 1.6666&hellip;n + o(1) of the obvious algorithm. we describe a similar algorithm for c &equals;4 colors whose average complexity on the 4n equally probable inputs is 761311/402850n + o(log n) &equals; 1.8898&hellip;n + o(log n), substantially better than the expected complexity 9/4n + o(1) &equals; 2.25n + o(1) of the obvious algorithm.
testing bipartiteness of geometric intersection graphs. we show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of an intersection graph of balls in d-dimensional euclidean space, in time o(n log n). more generally, we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric objects. our algorithms for these problems return either a bipartition of the input or an odd cycle in its intersection graph. we also consider lower bounds for connectivity and k-colorability problems of geometric intersection graphs. for unit balls in d dimensions, connectivity testing has equivalent randomized complexity to construction of euclidean minimum spanning trees, and for line segments in the plane connectivity testing has the same lower bounds as hopcroft's point-line incidence testing problem; therefore, for these problems, connectivity is unlikely to be solved as efficiently as bipartiteness. for line segments or planar disks, testing k-colorability of intersection graphs for k > 2 is np-complete.
algorithms for distributional and adversarial pipelined filter ordering problems. pipelined filter ordering is a central problem in database query optimization. the problem is to determine the optimal order in which to apply a given set of commutative filters (predicates) to a set of elements (the tuples of a relation), so as to find, as efficiently as possible, the tuples that satisfy all of the filters. optimization of pipelined filter ordering has recently received renewed attention in the context of environments such as the web, continuous high-speed data streams, and sensor networks. pipelined filter ordering problems are also studied in areas such as fault detection and machine learning under names such as learning with attribute costs, minimum-sum set cover, and satisficing search. we present algorithms for two natural extensions of the classical pipelined filter ordering problem: (1) a distributional-type problem where the filters run in parallel and the goal is to maximize throughput, and (2) an adversarial-type problem where the goal is to minimize the expected value of multiplicative regret. we present two related algorithms for solving (1), both running in time o(n2), which improve on the o(n3 log n) algorithm of kodialam. we use techniques from our algorithms for (1) to obtain an algorithm for (2).
approximating the distance to properties in bounded-degree and general sparse graphs. we address the problem of approximating the distance of bounded-degree and general sparse graphs from having some predetermined graph property p. that is, we are interested in sublinear algorithms for estimating the fraction of edge modifications (additions or deletions) that must be performed on a graph so that it obtains p. this fraction is taken with respect to a given upper bound m on the number of edges. in particular, for graphs with degree bound d over n vertices, m &equals; dn. to perform such an approximation the algorithm may ask for the degree of any vertex of its choice, and may ask for the neighbors of any vertex. the problem of estimating the distance to having a property was first explicitly addressed by parnas et al. [2006]. in the context of graphs this problem was studied by fischer and newman [2007] in the dense graphs model. in this model the fraction of edge modifications is taken with respect to n2, and the algorithm may ask for the existence of an edge between any pair of vertices of its choice. fischer and newman showed that every graph property that has a testing algorithm in this model, with query complexity independent of the size of the graph, also has a distance approximation algorithm with query complexity that is independent of the size of graph. in this work we focus on bounded-degree and general sparse graphs, and give algorithms for all properties shown to have efficient testing algorithms by goldreich and ron [2002]. specifically, these properties are k-edge connectivity, subgraph freeness (for constant-size subgraphs), being an eulerian graph, and cycle freeness. a variant of our subgraph-freeness algorithm approximates the size of a minimum vertex cover of a graph in sublinear time. this approximation improves on a recent result of parnas and ron [2007].
bicriteria approximation tradeoff for the node-cost budget problem. we consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. the goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. the best result known prior to this work guaranteed a (2, o(log n)) bicriteria approximation, that is, the solution's profit is at least a fraction of 1/o(log n) of an optimum solution respecting the budget, while its cost is at most twice the given budget. we improve these results and present a bicriteria tradeoff that, given any &epsiv; &isin; (0,1], guarantees a (1 + &epsis;, o(1/&epsiv; log n))-approximation.
a polynomial-time approximation scheme for embedding hypergraph in a cycle. we consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized. the minimum congestion hypergraph embedding in a cycle problem is known to be np-hard and its graph version, the minimum congestion graph embedding in a cycle, is solvable in polynomial-time. furthermore, for the graph problem, a polynomial-time approximation scheme for the weighted version is known. for the hypergraph model, several approximation algorithms with a ratio of two have been previously published. a recent paper reduced the approximation ratio to 1.5. we present a polynomial-time approximation scheme in this article, settling the debate regarding whether the problem is polynomial-time approximable.
throughput maximization of real-time scheduling with batching. we consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. the input to the problem consists of n jobs and k parallel machines. each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. each family is associated with a processing time. jobs that belong to the same family can be batched and executed together on the same machine. the processing time of each batch is the processing time of the family of jobs it contains. the goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. we give constant factor (4 or 4 + &epsiv;) approximation algorithms for two variants of the problem, depending on the precise representation of the input. when the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + &epsiv;, respectively. we also give approximation algorithms for two special cases when all release times are the same.
linear time 3-approximation for the mast problem. given a set of leaf-labeled trees with identical leaf sets, the well-known maximum agreement subtree (mast) problem consists in finding a subtree homeomorphically included in all input trees and with the largest number of leaves. mast and its variant called maximum compatible tree (mct) are of particular interest in computational biology. this article presents a linear-time approximation algorithm to solve the complement version of mast, namely identifying the smallest set of leaves to remove from input trees to obtain isomorphic trees. we also present an o(n2 + kn) algorithm to solve the complement version of mct. for both problems, we thus achieve significantly lower running times than previously known algorithms. fast running times are especially important in phylogenetics where large collections of trees are routinely produced by resampling procedures, such as the nonparametric bootstrap or bayesian mcmc methods.
online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles. we present randomized algorithms for online conflict-free coloring (cf in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. in all three cases, the coloring algorithms use o(log n) colors, with high probability. we also present a deterministic algorithm for online cf coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using o(log3n) colors. this is the first efficient (i.e, using polylog(n) colors) deterministic online cf coloring algorithm for this problem.
rigorous results for random (2+p)-sat. in recent years there has been significant interest in the study of random k-sat formulae. for a given set of n boolean variables, let bk denote the set of all possible disjunctions of k distinct, non-complementary literals from its variables (k-clauses). a random k-sat formula fk (n;m) is formed by selectinguniformly and independently m clauses from bk and takingtheir conjunction. motivated by insights from statistical mechanics that suggest a possible relationship between the "order" of phase transitions and computational complexity, monasson and zecchina (phys. rev. e 56(2) (1997) 1357) proposed the random (2+p)-sat model: for a given p . [0; 1], a random (2 + p)-sat formula, f2+p(n;m), has m randomly chosen clauses over n variables, where pm clauses are chosen from b3 and (1 - p)m from b2. usingthe heuristic "replica method" of statistical mechanics, monasson and zecchina gave a number of non-rigorous predictions on the behavior of random (2 + p)-sat formulae. in this paper we give the 1rst rigorous results for random (2 + p)-sat, including the following surprising fact: for p &le; 2/5, with probability 1 - o(1), a random (2 + p)-sat formula is satisfiable if its 2-sat subformula is satisfiable. that is, for p 6 2=5, random (2 + p)-sat behaves like random 2-sat.
infinite trees and completely iterative theories: a coalgebraic view. infinite trees form a free completely iterative theory over any given signature--this fact, proved by elgot, bloom and tindell, turns out to be a special case of a much more general categorical result exhibited in the present paper. we prove that whenever an endofunctor h of a category has final coalgebras for all functors h(-) + x, then those coalgebras, tx, form a monad. this monad is completely iterative, i.e., every guarded system of recursive equations has a unique solution. and it is a free completely iterative monad on h. the special case of polynomial endofunctors of the category set is the above mentioned theory, or monad, of infinite trees.this procedure can be generalized to monoidal categories satisfying a mild side condition: if, for an object h, the endofunctor h ⊗ _ + i has a final coalgebra, t, then t is a monoid. this specializes to the above case for the monoidal category of all endofunctors.
inheritance of workflows: an approach to tackling problems related to change. inheritance is one of the key issues of object-orientation. the inheritance mechanism allows for the definition of a subclass which inherits the features of a specific superclass. when adapting a workflow process definition to specific needs (ad-hoc change) or changing the structure of the workflow process as a result of reengineering efforts (evolutionary change), inheritance concepts are useful to check whether the new workflow process inherits some desirable properties of the old workflow process. today's workflow management systems have problems dealing with both ad-hoc changes and evolutionary changes. as a result, a workflow management system is not used to support dynamically changing workflow processes or the workflow processes are supported in a rigid manner, i.e., changes are not allowed or handled outside of the workflow management system. in this paper, we propose inheritance-preserving transformation rules for workflow processes and show that these rules can be used to avoid problems such as the "dynamic-change bug." the dynamic-change bug refers to errors introduced by migrating a case (i.e., a process instance) from an old process definition to a new one. a transfer from an old process to a new process can lead to duplication of work, skipping of tasks, deadlocks, and livelocks. restricting change to the inheritance-preserving transformation rules guarantees transfers without any of these problems. moreover, the transformation rules can also be used to extract aggregate management information in case more than one version of a workflow process cannot be avoided.
balances for fixed points of primitive substitutions. an infinite word defined over a finite alphabet a is balanced if for any pair (ω,ω') of factors of the same length and for any letter a in the alphabet ||ω|a - |ω'|a| ≤ 1, where |ω|a denotes the number of occurrences of the letter a in the word ω. in this paper, we generalize this notion and introduce a measure of balance for an infinite sequence. in the case of fixed points of primitive substitutions, we show that the asymptotic behaviour of this measure is in part ruled by the spectrum of the incidence matrix associated with the substitution. connections with frequencies of letters and other balance properties are also discussed.
on final coalgebras of continuous functors. continuous endofunctors f of locally finitely presentable categories carry a natural metric on their final coalgebra. whenever f(0) has an element, this metric is proved to be a cauchy completion of the initial algebra of f. this is illustrated on the poset of real numbers represented as a final coalgebra of an endofunctor of pos by pavlovic´ and pratt. under additional assumptions on the locally finitely presentable category, all finitary endofunctors are proved to have a final coalgebra constructed in ω + ω steps of the natural iteration construction.
the intersection of algebra and coalgebra. presheaf categories are well-known to be varieties of algebras and covarieties of coalgebras. we prove the converse: if a category is a variety as well as a covariety, then it is a presheaf category. our main result is that all coalgebras on a set functor h form a presheaf category iff h is a reduction of a polynomial functor.
deciding knowledge in security protocols under equational theories. the analysis of security protocols requires precise formulations of the knowledge of protocol participants and attackers. in formal approaches this knowledge is often treated in terms of message deducibility and indistinguishability relations. in this paper we study the decidability of these two relations. the messages in question may employ functions (encryption, decryption, etc.) axiomatized in an equational theory. one of our main positive results says that deducibility and indistinguishability are both decidable in polynomial time for a large class of equational theories. this class of equational theories is defined syntactically and includes, for example, theories for encryption, decryption, and digital signatures. we also establish general decidability theorems for an even larger class of theories. these theorems require only loose, abstract conditions, and apply to many other useful theories, for example with blind digital signatures, homomorphic encryption, xor, and other associative-commutative functions.
on abstract data types presented by multiequations. equational presentation of abstract data types is generalized to presentation by multiequations, i.e., exclusive-or's of equations, in order to capture parametric data types such as array or set. multiinitial-algebra semantics for such data types is introduced. classes of algebras described by multiequations are characterized.
formal parametric polymorphism. a polymorphic function is parametric if its behavior does not depend on the type at which it is instantiated. starting with reynolds' work, the study of parametricity is typically semantic. in this paper, we develop a syntactic approach to parametricity, and a formal system that embodies this approach: system r . girard's system f deals with terms and types; r is an extension of f that deals also with relations between types. in r **, it is possible to derive theorems about functions from their types, or &ldquo;theorems for free&rdquo;, as wadler calls them. an easy &ldquo;theorem for free&rdquo; asserts that the type &forall;xx&rarr; bool contains only constant functions; this is not provable in f. there are many harder and more substantial examples. various metatheorems can also be obtained, such as a syntactic version of reynolds' abstraction theorem.
private authentication. frequently, communication between two principals reveals their identities and presence to third parties. these privacy breaches can occur even if security protocols are in use; indeed, they may even be caused by security protocols. however, with some care, security protocols can provide authentication for principals that wish to communicate while protecting them from monitoring by third parties. we discuss the problem of private authentication and present two protocols for private authentication of mobile principals. our protocols allow two mobile principals to communicate when they meet at a location if they wish to do so, without the danger of tracking by third parties. we also present the analysis of one of the protocols in the applied pi calculus. we establish authenticity and secrecy properties. although such properties are fairly standard, their formulation in the applied pi calculus makes an original use of process equivalences. in addition, we treat identity-protection properties, thus exploring a formal model of privacy.
linearisability on datalog programs. linear datalog programs are programs whose clauses have at most one intensional atom in their bodies. we explore syntactic classes of datalog programs (syntactically non-linear) which turn out to express no more than the queries expressed by linear datalog programs. in particular, we investigate linearisability of (database queries corresponding to) piecewise linear datalog programs and chain queries: (a) we prove that piecewise linear datalog programs can always be transformed into linear datalog programs, by virtue of a procedure which performs the transformation automatically. the procedure relies upon conventional logic program transformation techniques. (b) we identify a new class of linearisable chain queries, referred to as pseudo-regular, and prove their linearisability constructively, by generating, for any given pseudo-regular chain query, the datalog program corresponding to it.
the expressiveness of dac. we define a new logic-based query language, called dac, which is an extension of data-log. a dac(w(n),h(n))(b(n))-program consists of a family of datalog programs pn such that w(n),h(n),b(n) bound the width of rules, the number of rules, and the recursion depth of any pn, respectively. we exhibit queries which are not datalog expressible but are dac expressible. we also prove non-expressiveness results for dac and we infer various strict hierarchies obtained by allowing more rapidly growing functions on the bound parameters.
projective topology on bifinite domains and applications. we revisit extension results from continuous valuations to radon measures for bifinite domains. in the framework of bifinite domains, the prokhorov theorem (existence of projective limits of radon measures) appears as a natural tool, and helps building a bridge between measure theory and domain theory. the study we present also fills a gap in the literature concerning the coincidence between projective and lawson topology for bifinite domains. motivated by probabilistic considerations, we study the extension of measures in order to define borel measures on the space of maximal elements of a bifinite domain.
open block scheduling in optical communication networks. in this paper the process of data transmission in star coupled optical communication networks is modelled as a shop-type scheduling problem, where channels (wavelengths) are treated as machines. we formulate an open block problem with the minimum makespan objective (o b||cmax) in which a relation of a new type between the operations of each job is introduced: any two operations of a job have identical processing times and may be processed either simultaneously (in a common block) or, alternatively, at disjoint time intervals. we show that the problem is polynomially solvable for 4 machines, np-hard for 6 machines and strongly np-hard for a variable number of machines. for the case of a variable number of machines we present a polynomial time √2-approximation algorithm and prove that there is no polynomial time ρ-approximation algorithm with ρ < 11/10, unless p = np. for the case when the number of machines is fixed, we show that the problem admits a linear time ptas. in addition, we show that the two-machine problem with release dates is np-hard in the strong sense.
containers: constructing strictly positive types. we introduce the notion of a martin-löf category--a locally cartesian closed category with disjoint coproducts and initial algebras of container functors (the categorical analogue of w-types)--and then establish that nested strictly positive inductive and coinductive types, which we call strictly positive types, exist in any martin-löf category.central to our development are the notions of containers and container functors. these provide a new conceptual analysis of data structures and polymorphic functions by exploiting dependent type theory as a convenient way to define constructions in martin-löf categories. we also show that morphisms between containers can be full and faithfully interpreted as polymorphic functions (i.e. natural transformations) and that, in the presence of w-types, all strictly positive types (including nested inductive and coinductive types) give rise to containers.