waashk/dblp huggingface dataset:
change of order for regular chains in positive dimension. we discuss changing the variable order for a regular chain in positive dimension. this quite general question has applications going from implicitization problems to the symbolic resolution of some systems of differential algebraic equations. we propose a modular method, reducing the problem to computations in dimension zero and one. the problems raised by the choice of the specialization points and the lack of the (crucial) information of what are the free and algebraic variables for the new order are discussed. strong (but not unusual) hypotheses for the initial regular chain are required; the main required subroutines are change of order in dimension zero and a formal newton iteration.
curves and surfaces represented by polynomial support functions. this paper studies shapes (curves and surfaces) which can be described by (piecewise) polynomial support functions. the class of these shapes is closed under convolutions, offsetting, rotations and translations. we give a geometric discussion of these shapes and present methods for the approximation of general curves and surfaces by them. based on the rich theory of spherical spline functions, this leads to computational techniques for rational curves and surfaces with rational offsets, which can deal with shapes without inflections/parabolic points.
algebraic cycles from a computational point of view. the hodge conjecture implies decidability of the question whether a given topological cycle on a smooth projective variety over the field of algebraic complex numbers can be represented by an algebraic cycle. we discuss some details concerning this observation, and then propose that it suggests going on to actually implement an algorithmic search for algebraic representatives of classes which are known to be hodge classes.
swept regions and surfaces: modeling and volumetric properties. we consider ''swept regions'' @w and ''swept hypersurfaces'' b in r^n^+^1 (and especially r^3) which are a disjoint union of subspaces @w"t=@w@?@p"t or b"t=b@?@p"t obtained from a varying family of affine subspaces {@p"t:t@?@c}. we concentrate on the case where @w and b are obtained from a skeletal structure (m,u). this generalizes the blum medial axis m of a region @w, which consists of the centers of interior spheres tangent to the boundary b at two or more points, with u denoting the vectors from the centers of the spheres to the points of tangency. we extend methods developed for skeletal structures so that they can be deduced from the properties of the individual intersections @w"t or b"t and a relative shape operator s"r"e"l, which we introduce to capture changes relative to the varying family {@p"t}. we use these results to deduce modeling properties of the global b in terms of the individual b"t, and determine volumetric properties of regions @w expressed as global integrals of functions g on @w in terms of iterated integrals over the skeletal structure of @w"t which is then integrated over the parameter space @c.
seminormal rings (following thierry coquand). the traverso-swan theorem says that a reduced ring a is seminormal if and only if the natural homomorphism pica->pica[x] is an isomorphism [c. traverso, seminormality and the picard group, ann. sc. norm. sup. pisa 24 (1970) 585-595; r.g. swan, on seminormality, j. algebra 67 (1980) 210-229]. we give here all the details needed to understand the elementary constructive proof for this result given by coquand in [t. coquand, on seminormality, j. algebra 305 (2006) 577-584]. this example is typical of a new constructive method. the final proof is simpler than the initial classical one. more important: the classical argument by absurdum using ''an abstract ideal object'' is deciphered with a general technique based on the following idea: purely ideal objects constructed using tem and choice may be replaced by concrete objects that are ''finite approximations'' of these ideal objects.
on multiplier sequences. in the present paper we consider real polynomials in one real variable of a given degree n. such a polynomial is called hyperbolic if it has only real roots. a finite multiplier sequence of lengthn+1 (fms(n+1)) is a tuple (c"0,...,c"n), c"i@?r, such that if @?"i"="0^nb"ix^n^-^i, b"i@?r, is a hyperbolic polynomial, then @?"i"="0^nc"ib"ix^n^-^i is also such a polynomial. the set of fms(n+1) coincides with the set of tuples such that @?"i"="0^nc"n^ic"ix^n^-^i is a hyperbolic polynomial with all roots of the same sign. in the paper we prove several geometric properties of the set of fms(n+1) formulated in terms of its stratification (defined by the multiplicity vectors of the polynomials) and of the whitney property (the curvilinear distance to be equivalent to the euclidean one).
the moving curve ideal and the rees algebra. the rees algebra of an ideal in a commutative ring is the quotient of a polynomial ring by its ideal of defining relations. for a polynomial ring in two variables, this ideal was discovered independently by the geometric modeling community, where it is called the moving curve ideal. we review some properties of the rees algebra and discuss one result and one conjecture concerning the structure of the moving curve ideal and its relation to adjoint curves. some parts of the paper are purely expository.
on the complexity of real root isolation using continued fractions. we present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. one motivation is to explain the method's good performance in practice. we derive an expected complexity bound of o@?"b(d^6+d^4@t^2), where d is the polynomial degree and @t bounds the coefficient bit size, using a standard bound on the expected bit size of the integers in the continued fraction expansion, thus matching the current worst-case complexity bound for real root isolation by exact methods (sturm, descartes and bernstein subdivision). moreover, using a homothetic transformation we improve the expected complexity bound to o@?"b(d^3@t). we compute the multiplicities within the same complexity and extend the algorithm to non-square-free polynomials. finally, we present an open-source c++ implementation in the algebraic library synaps, and illustrate its completeness and efficiency as compared to some other available software. for this we use polynomials with coefficient bit size up to 8000 bits and degree up to 1000.
on different generalizations of episturmian words. in this paper we study some classes of infinite words generalizing episturmian words, and analyse the relations occurring among such classes. in each case, the reversal operator r is replaced by an arbitrary involutory antimorphism @q of the free monoid a^*. in particular, we define the class of @q-words with seed, whose ''standard'' elements (@q-standard words with seed) are constructed by an iterative @q-palindrome closure process, starting from a finite word u"0 called the seed. when the seed is empty, one obtains @q-words; episturmian words are exactly the r-words. one of the main theorems of the paper characterizes @q-words with seed as infinite words closed under @q and having at most one left special factor of each length n>=n (where n is some nonnegative integer depending on the word). when n=0 we call such words @q-episturmian. further results on the structure of @q-episturmian words are proved. in particular, some relationships between @q-words (with or without seed) and @q-episturmian words are shown.
smooth words on 2-letter alphabets having same parity. in this paper, we consider smooth words over 2-letter alphabets {a,b}, where a,b are integers having same parity, with 0
simple permutations: decidability and unavoidable substructures. we prove that it is decidable whether a finitely based permutation class contains infinitely many simple permutations, and establish an unavoidable substructure result for simple permutations: every sufficiently long simple permutation contains an alternation or oscillation of length k.
energy conservation in wireless sensor networks and connectivity of graphs. in wireless sensor networks (wsns), the energy source is usually a battery cell, which is impossible to recharge while wsns are working. therefore, one of the main issues in wireless sensor networks is how to prolong the network lifetime of wsns with certain energy sources as well as how to maintain coverage and connectivity. in this paper, we consider wireless sensor networks satisfying the case that each node either monitors one target or is just for connection. assume that the wireless sensor network has l targets, and that each is monitored by k sensor nodes. if k=2 and the graph g corresponding to the wireless sensor network is (l+max{1,l-4})-connected, or k>=3 and g is (l(k-1)+1)-connected, then we can find k (the maximum number) disjoint sets, each of which completely covers all the targets and remains connected to one of the central processing nodes. the disjoint sets are activated successively, and only the sensor nodes from the active set are responsible for monitoring the targets and connectivity; all other nodes are in a sleep mode. in addition, we also give the related algorithms to find the k disjoint sets.
graph automata. magmoids satisfying the 15 fundamental equations of graphs, namely graphoids, are introduced. automata on directed hypergraphs are defined by virtue of a relational graphoid. the closure properties of the so-obtained class are investigated, and a comparison is being made with the class of syntactically recognizable graph languages.
on the hardness of optimization in power-law graphs. our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from internet and world wide web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. there is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: is combinatorial optimization in power-law graphs easy? does the answer depend on the power-law exponent @b? our main result is the proof that many classical np-hard graph-theoretic optimization problems remain np-hard on power-law graphs for certain values of @b. in particular, we show that some classical problems, such as clique and coloring, remain np-hard for all @b>=1. moreover, we show that all the problems that satisfy the so-called ''optimal substructure property'' remain np-hard for all @b>0. this includes classical problems such as minimum vertex cover, maximum independent set, and minimum dominating set. our proofs involve designing efficient algorithms for constructing graphs with prescribed degree sequences that are tractable with respect to various optimization problems.
the computational complexity of the parallel knock-out problem. we consider computational complexity questions related to parallel knock-out schemes for graphs. in such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. we show that the problem of whether, for a given bipartite graph, such a scheme can be found that eliminates every vertex is np-complete. moreover, we show that, for all fixed positive integers k>=2, the problem of whether a given bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) k rounds is np-complete. for graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time. we also show that r-regular graphs with r>=1, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.
approximating a vehicle scheduling problem with time windows and handling times. in this paper, we study a problem of finding a vehicle scheduling to process a set of n jobs which are located in an asymmetric metric space. each job j has a positive handling time h(j), a time window [r(j),d(j)], and a benefit b(j). we consider the following two problems: max-vsp asks to find a schedule for a single vehicle to process a subset of jobs with the maximum benefit; and min-vsp asks to find a schedule to process all given jobs with the minimum number of vehicles. we first give an o(@rn^3^+^@c) time algorithm that delivers a 2-approximate solution to max-vsp, where @r=max"j","j"^"'(d(j)-r(j))/h(j^') and @c is the maximum number of jobs that can be processed by the vehicle after processing a job j and before visiting the processed job j again by deadline d(j). we then present an o(@rn^4^+^@c) time algorithm that delivers a 2h(n)-approximate solution to min-vsp, where h(n) is the nth harmonic number.
the cost of offline binary search tree algorithms and the complexity of the request sequence. in evaluating the performance of online algorithms for search trees, one wants to compare them to the best offline algorithm available. in this paper we lower bound the cost of an optimal offline binary search tree using the kolmogorov complexity of the request sequence. we obtain several applications for this result. first, any offline binary search tree algorithm can be at most a constant factor away from the entropy of the process producing the request sequence. second, for a fraction 1-1/2^m of request sequences of length m on n items the cost of any offline algorithm is @w(m(logn-1)). third, the expected cost of splay trees is within a constant factor of the expected cost of an optimal offline binary search tree algorithm in a subset of markov chains.
another proof of soittola's theorem. soittola's theorem characterizes r"+- or n-rational formal power series in one variable among the rational formal power series with nonnegative coefficients. we present here a new proof of the theorem based on soittola's and perrin's proofs together with some new ideas that allows us to separate algebraic and analytic arguments.
competitive graph searches. we exemplify an optimization criterion for divide-and-conquer algorithms with a technique called generic competitive graph search. the technique is then applied to solve two problems arising from biocomputing, so-called common connected components and cograph sandwich. the first problem can be defined as follows: given two graphs on the same set of n vertices, find the coarsest partition of the vertex set into subsets which induce connected subgraphs in both input graphs. the second problem is an instance of sandwich problems: given a partial subgraph g"1 of g"2, find a partial subgraph g of g"2 that is partial supergraph of g"1 (sandwich), and that is a cograph. for the former problem our generic algorithm not only achieves the current best known performance on arbitrary graphs and forests, but also improves by a logn factor when the input is made of planar graphs. however, our complexity for intervals graphs is slightly lower than a recent result. for the latter problem, we first study the relationship between the common connected components problem and the cograph sandwich problem, then, using our competitive graph search paradigm, we improve the computation of cograph sandwiches from o(n(n+m)) down to o(n+mlog^2n), where n is the number of vertices and m of total edges.
parallel-machine scheduling with time dependent processing times. in the literature, most of the parallel-machine scheduling problems, in which the processing time of a job is a linear function of its starting time, are proved to be np-hard. in this paper, we study a parallel-machine scheduling problem in which the processing time of a job is a linear function of its starting time. the objectives are to minimize the total completion of all jobs and the total load on all machines respectively. we consider two linear functions of job starting time and show that the problems are polynomially solvable.
a fast asymptotic approximation scheme for bin packing with rejection. ''bin packing with rejection'' is the following problem: given a list of items with associated sizes and rejection costs, find a packing into unit bins of a subset of the list such that the number of bins used plus the sum of rejection costs of unpacked items is minimized. we show that bin packing with rejection can be reduced to n multiple knapsack problems and, based on techniques for the multiple knapsack problem, we give a fast asymptotic polynomial time approximation scheme,''reject&pack'', with time complexity o(n^o^(^@e^^^-^^^2^)). this improves a recent approximation scheme given by epstein, which has time complexity o(n^o^(^(^@e^^^-^^^4^)^^^@e^^^^^^^-^^^^^^^1^)). we also show that reject&pack can be extended to variable-sized bin packing with rejection and give an asymptotic polynomial time approximation scheme.
approximating the online set multicover problems via randomized winnowing. in this paper, we consider the weighted online set k-multicover problem. in this problem, we have a universe v of elements, a family s of subsets of v with a positive real cost for every s@?s, and a ''coverage factor'' (positive integer) k. a subset {i"0,i"1,...}@?v of elements are presented online in an arbitrary order. when each element i"p is presented, we are also told the collection of all (at least k) sets s"i"""p@?s and their costs to which i"p belongs and we need to select additional sets from s"i"""p if necessary such that our collection of selected sets contains at leastk sets that contain the element i"p. the goal is to minimize the total cost of the selected sets. in this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of [n. littlestone, learning quickly when irrelevant attributes abound: a new linear-threshold algorithm, machine learning 2 (1988) 285-318]. this algorithm generalizes and improves some earlier results in [n. alon, b. awerbuch, y. azar, n. buchbinder, j. naor, a general approach to online network optimization problems, in: proceedings of the 15th acm-siam symposium on discrete algorithms, 2004, pp. 570-579; n. alon, b. awerbuch, y. azar, n. buchbinder, j. naor, the online set cover problem, in: proceedings of the 35th annual acm symposium on the theory of computing, 2003, pp. 100-105]. we also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [n. alon, b. awerbuch, y. azar, n. buchbinder, j. naor, the online set cover problem, in: proceedings of the 35th annual acm symposium on the theory of computing, 2003, pp. 100-105].
move-optimal gossiping among mobile agents. mobile-agent-based distributed systems are attracting widespread attention because of their adaptability and flexibility; mobile agents traverse the system and carry out a task at each node. in mobile-agent-based systems, gossip is a fundamental task in cooperation among mobile agents. it requires one to accomplish all-to-all information exchange over all agents so that each agent can obtain the information each agent initially has. while rendezvous algorithms, which require that all agents rendezvous on a node at the same time, can achieve this requirement, it takes excessive cost for our objective. in this paper, we introduce the mobile agent gossip problem, in which each agent must obtain the information all other agents have. each agent p"i can obtain the information of p"j(
decidability and syntactic control of interference. we investigate the decidability of observational equivalence and approximation in reynolds' ''syntactic control of interference'' (sci), a prototypical functional-imperative language in which covert interference between functions and their arguments is prevented by the use of an affine typing discipline. by associating denotations of terms in a fully abstract ''relational'' model of finitary basic sci (due to reddy) with multitape finite state automata, we show that observational approximation is not decidable (even at first order), but that observational equivalence is decidable for all terms. we then consider the same problems for basic sci extended with non-local control in the form of backwards jumps. we show that both observational approximation and observational equivalence are decidable in this ''observably sequential'' version of the language by describing a fully abstract games model in which strategies are regular languages.
constructibility and decidability versus domain independence and absoluteness. we develop a unified framework for dealing with constructibility and absoluteness in set theory, decidability of relations in effective structures (like the natural numbers) and domain independence of queries in database theory. our framework and results suggest that domain-independence and absoluteness might be the key notions in a general theory of constructibility, predicativity and computability.
minimality considerations for ordinal computers modeling constructibility. we describe a simple model of ordinal computation which can compute truth in the constructible universe. we try to use well-structured programs and direct limits of states at limit times whenever possible. this may make it easier to define a model of ordinal computation within other systems of hypercomputation, especially systems inspired by physical models. we write a program to compute truth in the constructible universe on an ordinal register machine. we prove that the number of registers in a well-structured universal ordinal register machine is always >=4, greater than the minimum number of registers in a well-structured universal finite-time natural number-storing register machine, but that it can always be kept finite. we conjecture that this number is four. we compare the efficiency of our program which computes the constructible sets to that of a similar program for an ordinal turing machine.
dynamics of a generic brownian motion: recursive aspects. we study the local fluctuations of brownian motions which are represented by infinite binary strings which are random in the sense of kolmogorov-chaitin. we show how the dynamical properties of such a brownian motion at a point depend on its recursive properties.
itemset frequency satisfiability: complexity and axiomatization. computing frequent itemsets is one of the most prominent problems in data mining. we study the following related problem, called freqsat, in depth: given some itemset-interval pairs, does there exist a database such that for every pair the frequency of the itemset falls into the interval? this problem is shown to be np-complete. the problem is then further extended to include arbitrary boolean expressions over items and conditional frequency expressions in the form of association rules. we also show that, unless p equals np, the related function problem-find the best interval for an itemset under some frequency constraints-cannot be approximated efficiently. furthermore, it is shown that freqsat is recursively axiomatizable, but that there cannot exist an axiomatization of finite arity.
interval-valued computations and their connection with pspace. at the conference cie 2005, the first author introduced a new model for analog computations, namely interval-valued computations. in this model, computations work on the so-called interval-valued bytes, which are special subsets of the interval [0,1) rather than a finite sequence of bits. the question was posed there, which complexity is needed to solve pspace-complete problems in this paradigm. in this paper, after formalizing the computational model, we answer this question. we show that the validity problem of quantified propositional formulae is decidable by a linear interval-valued computation. as a consequence, all polynomial space problems are decidable by a polynomial interval-valued computation. furthermore, it is proven that pspace coincides with the class of languages which are decidable by a restricted polynomial interval-valued computation.