waashk/dblp huggingface dataset:
on-line algorithms for the dynamic traveling repair problem. we consider the dynamic traveling repair problem in which requests with deadlines arrive through time on points in a metric space. servers move from point to point at constant speed. the goal is to plan the motion of servers so that the maximum number of requests are met by their deadline. we consider a restricted version of the problem in which there is a single server and the length of time between the arrival of a request and its deadline is constant. we give upper bounds for the competitive ratio of two very natural algorithms as well as several lower bounds for any deterministic algorithm. most of the results in this paper are expressed as a function of β, the diameter of the metric space. in particular, we prove that the upper bound given for one of the two algorithms is within a constant factor of the best possible competitive ratio.
algorithms for power savings. this paper examines two different mechanisms for saving power in battery-operated embedded systems. the first is that the system can be placed in a sleep state if it is idle. however, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. the second way in which power savings can be achieved is by varying the speed at which jobs are run. we utilize a power consumption curve p(s). which indicates the power consumption level given a particular speed. we assume that p(s) and p(s)/s are convex. the problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its arrival time and before its deadline. although each problem has been considered separately, this is the first theoretical analysis of systems which can use both mechanisms. we give an off line algorithm which is within a factor of three of the optimal algorithm. we also give an online algorithm with a constant competitive ratio.
rank-maximal matchings. suppose that each member of a set a of applicants ranks a subset of a set p of posts in an order of preference, possibly involving ties. a matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. a greedy matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. this is a relevant concept in any practical matching situation and it was first studied by irving [8].we define the bipartite graph g = (a u p,ε), where ε consists of all pairs (a, p) such that post p appears in the preference list of applicant a. each edge (a, p) has a rank i, which means that post p is an ith choice for applicant a. the traditional solution of computing a greedy matching in g would be to use the hungarian algorithm to compute a maximum weight matching by assigning a suitably steeply decreasing sequence of weights to the edges. this would result in an algorithm with worst case running time rn(m + n log n) and the space requirement &theta;(rm), where n is the number of vertices, m is the number of edges and r is the largest rank of an edge.here, we describe two algorithms to compute a greedy matching that improve upon this algorithm. we give a combinatorial algorithm with running time o(min(n + c,c&radic;n)m), where c &le; r is the maximal rank of an edge used in a greedy matching. this algorithm works in phases and uses the maximum cardinality matching algorithm. we also give an o(cnm) algorithm that tackles the problem of large edge weights introduced by the hungarian algorithm. this algorithm uses scaling and works in phases. the space requirement of both these algorithms is o(m).
randomized pursuit-evasion with limited visibility. we study the following pursuit-evasion game: one or more hunters are seeking to capture an evading rabbit on a graph. at each round, the rabbit tries to gather information about the l ocation of the hunters but it can see them only if they are located on adjacent nodes. we show that two hunters suffice for catching rabbits with limited visibility with high probability. we distinguish between reactive rabbits who who move only when the hunter is visible and general rabbits can employ more sophisticated strategies. we present polynomial time algorithms that decide whether a graph g is hunter-win, that is, if a single hunter can capture a rabbit of either kind on g.
the phase transition in random horn satisfiability and its algorithmic implications. let c > 0 be a constant, and φ be a random horn formula with n variables and m = c . 2n clauses, chosen uniformly at random (with repetition) from the set of all nonempty horn clauses in the given variables. by analyzing pur, a natural implementation of positive unit resolution, we show that limn→∞ pr(φ is satisfiable) = 1 - f(e-c), where f(x) = (1 - x)(1 - x2)(1 - x4) (1 - x8) .... our method also yields as a byproduct an average-case analysis of this algorithm.
a fully combinatorial algorithm for submodular function minimization. this paper presents a strongly polynomial algorithm for submodular function minimization using only additions, subtractions, comparisons, and oracle calls for function values.
packing steiner trees. the steiner packing problem is to find the maximum number of edge-disjoint subgraphs of a given graph g that connect a given set of required points s. this problem is motivated by practical applications in vlsi- layout and broadcasting, as well as theoretical reasons. in this paper, we study this problem and present an algorithm with an asymptotic approximation factor of &verbar;s&verbar;/4. this gives a sufficient condition for the existence of k edge-disjoint steiner trees in a graph in terms of the edge-connectivity of the graph. we will show that this condition is the best possible if the number of terminals is 3. at the end, we consider the fractional version of this problem, and observe that it can be reduced to the minimum steiner tree problem via the ellipsoid algorithm.
a primal-dual schema based approximation algorithm for the element connectivity problem. the element connectivity problem falls in the category of survivable network design problems-it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. the edge version is by now well understood from the view-point of approximation algorithms [williamson et al., combinatorica 15 (1995) 435-454; goemans et al., in: soda '94, 223-232; jain, combinatorica 21 (2001) 39-60], but very little is known about the vertex version. in our problem, vertices are partitioned into two sets: terminals and nonterminals. only edges and nonterminals can fail--we refer to them as elements--and only pairs of terminals have connectivity requirements, specifying the number of element-disjoint paths required. our algorithm achieves an approximation guarantee of factor 2hk, where k is the largest requirement and hn = 1 + ½ +... + 1/n. besides providing possible insights for solving the vertex-disjoint paths version, the element connectivity problem is of independent interest, since it models a realistic situation.
equilibria for economies with production: constant-returns technologies and production planning constraints. we consider the computation of equilibria in two economic models that generalize the exchange model by including production. in the constant returns model, each producer has a convex, constant-returns-to-scale, technology. in particular, this means that if the technology can output a certain quantity of a good using as input certain quantities of other goods, then scaling all these quantities by a common, non-negative, number also results in a technologically feasible plan. the technology also accomodates the no-free-lunch property, which says that it is not possible to produce something from nothing. at a given price, the producer picks a technologically feasible plan that maximizes her profit. associated with each consumer is an initial endowment of goods and a utility function that describes her preferences between various bundles of goods. at a given price, the consumer sells her initial endowment, thus obtaining a certain income, and demands the bundle of goods maximizing her utility among all bundles that she can afford at the given price with her income.
market equilibria for homothetic, quasi-concave utilities and economies of scale in production. eisenberg and gale (1959) gave a convex program for computing market equilibrium for fisher's model for linear utility functions, and eisenberg (1961) generalized this to concave homogeneous functions of degree one. we further generalize to:1. homothetic, quasi-concave utilities. this also helps extend eisenberg's result to concave homogeneous functions of arbitrary degree.2. we introduce the notion of a trading cone which enables us to compute market equilibrium in the presence of economies of scale in production provided differential pricing is allowed. applications to network pricing are provided.
an asymptotic approximation algorithm for 3d-strip packing. we present an asymptotic (2 + &epsilon;)-approximation algorithm for the 3d-strip packing problem, for any &epsilon; > 0. in the 3d-strip packing problem the input is a set l = {b1, b2,. . ., bn} of 3-dimensional boxes. each box bi has width, length, and height at most 1. the problem is to pack the boxes into a 3-dimensional bin b of width 1, length 1 and minimum height, so that the boxes do not overlap. we consider here only orthogonal packings without rotations; this means that the boxes are packed so that their faces are parallel to the faces of the bin, and rotations are not allowed. this algorithm improves on the previously best algorithm of miyazawa and wakabayashi which has asymptotic performance ratio of 2.64. our algorithm can be easily modified to a (4 + &epsilon;)-approximation algorithm for the 3d-bin packing problem.
on rectangle packing: maximizing benefits. we consider the following rectangle packing problem: given a set of rectangles, each of which is associated with a profit, we are requested to pack a subset of the rectangles into a bigger rectangle to maximize the total profit of rectangles packed. the rectangles may not overlap and may or may not be rotated. this problem is strongly np-hard even for packing squares with identical profits. a simple (3 + ε)-approximation algorithm is presented. we further improve the algorithm by showing a worst-case ratio of at most 5/2 + ε. finally we devise a (2 + ε)-approximation algorithm. a number of restricted cases are also considered.
algorithms for combining rooted triplets into a galled phylogenetic network. this paper considers the problem of determining whether a given set t of rooted triplets can be merged without conflicts into a galled phylogenetic network, and if so, constructing such a network. when the input t is dense, we solve the problem in o(|t|) time, which is optimal since the size of the input is &theta;(|t|). in comparison, the previously fastest algorithm for this problem runs in o(|t|2) time. next, we prove that the problem becomes np-hard if extended to non-dense inputs, even for the special case of simple phylogenetic networks. we also show that for every positive integer n, there exists some set t of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883&middot;|t| of the rooted triplets in t. on the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (>0.4166) of the rooted triplets in t.
performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining. we present the results of a large-scale experimental study of quartet-based methods (quartet cleaning and puzzling) for phylogeny reconstruction. our experiments include a broad range of problem sizes and evolutionary rates, and were carefully designed to yield statistically robust results despite the size of the sample space. we measure outcomes in terms of numbers of edges of the true tree correctly inferred by each method (true positives). our results indicate that these quartet-based methods are much less accurate than the simple and efficient method of neighbor-joining, particularly for data composed of short to medium length sequences. we support our experimental findings by theoretical results that suggest that quartet-cleaning methods are unlikely to yield accurate trees with less than exponentially long sequences. we suggest that a proposed reconstruction method should first be compared to the neighbor-joining method and further studied only if it offers a demonstrable practical advantage.
a polynomial time recognition algorithm for probe interval graphs. probe interval graphs were introduced to model a problem arising in a form of dna sequencing. this paper presents an &ogr;(n2) algorithm for recognizing probe interval graphs. this is the first polynomial time recognition algorithm for this class.
a 5/4-approximation algorithm for minimum 2-edge-connectivity. a 5/4-approximation algorithm is presented for the minimum cardinality 2-edge-connected spanning subgraph problem in undirected graphs. this improves the previous best approximation ratio of 4/3. it is shown that our ratio is tight with respect to current lower bounds, and any further improvement is possible only if new lower bounds are discovered.
hiding cliques for cryptographic security. we demonstrate how a well studied combinatorial optimization problem may be used as a new cryptographic primitive. the problem in question is that of finding a "large" clique in a random graph. while the largest clique in a random graph with n vertices and edge probability p is very likely to be of size about 2 \log_{1/p}{n}, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size \geq (1 + \epsilon)\log_{1/p}n with significant probability for any constant \epsilon > 0. we present a very simple method of exploiting this conjecture by ``hiding'' large cliques in random graphs. in particular, we show that if the conjecture is true, then when a large clique&mdash;of size, say, (1 + 2 \epsilon) \log_{1/p}{n}&mdash;is randomly inserted (``hidden'') in a random graph, finding a clique of size \geq (1 + \epsilon)\log_{1/p}{n} remains hard. our analysis also covers the case of high edge probabilities which allows us to insert cliques of size up to n^{1/4-\epsilon} ( \epsilon>0). our result suggests several cryptographic applications, such as a simple one-way function.
a deterministic subexponential algorithm for solving parity games. the existence of polynomial-time algorithms for the solution of parity games is a major open problem. the fastest known algorithms for the problem are randomized algorithms that run in subexponential time. these algorithms are all ultimately based on the randomized subexponential simplex algorithms of kalai and of matou&scaron;ek, sharir, and welzl. randomness seems to play an essential role in these algorithms. we use a completely different, and elementary, approach to obtain a deterministic subexponential algorithm for the solution of parity games. the new algorithm, like the existing randomized subexponential algorithms, uses only polynomial space, and it is almost as fast as the randomized subexponential algorithms mentioned above.
efficient pattern-matching with don't cares. we present a randomized algorithm for the string matching with don't cares problem. based on the simple fingerprint method of karp and rabin for ordinary string matching [4], our algorithm runs in time o(n log m) for a text of length n and a pattern of length m and is simpler and slightly faster than the previous algorithms [3, 5, 1].
fast approximation algorithm for minimum cost multicommodity flow. minimum-cost multicommodity flow problem is one of the classical optimization problems that arises in a variety of contexts. applications range from finding optimal ways to route information through communication networks to vlsi layout. in this paper, we describe an efficient deterministic approximation algorithm, which given that there exists a multicommodity flow of cost $b$ that satisfies all the demands, produces a flow of cost at most $(1+\delta)b$ that satisfies $(1-\epsilon)$-fraction of each demand. for constant $\delta$ and $\epsilon$, our algorithm runs in $o^*(kmn^2)$ time, which is an improvement over the previously fastest (deterministic) approximation algorithm for this problem due to plotkin, shmoys, and tardos, that runs in $o^*(k^2m^2)$ time.
routing and admission control in general topology networks with poisson arrivals. emerging high speed networks will carry traffic for services such as video-on-demand and video teleconferencing -- that require resource reservation along the path on which the traffic is sent. high bandwidth-delay product of these networks prevents circuit rerouting, i.e. once a circuit is routed on a certain path, the bandwidth taken by this circuit remains unavailable for the duration (holding time) of this circuit. as a result, such networks will need effective routing and admission control strategies. recently developed online routing and admission control strategies have logarithmic competitive ratios with respect to the admission ratio (the fraction of admitted circuits). such guarantees on performance are rather weak in the most interesting case where the rejection ratio of the optimum algorithm is very small or even 0. unfortunately, these guarantees can not be improved in the context of the considered models, making it impossible to use these models to identify algorithms that are going to perform well in practice. in this paper we develop routing and admission control strategies for a more realistic model, where the requests for virtual circuits between any two points arrive according to a poisson process and where the circuit holding times are exponentially distributed. our model is close to the one that was developed to analyse and tune the (currently used) strategies for managing traffic in long-distance telephone networks. we strengthen this model by assuming that the rates of the poisson processes (the ``traffic matrix'''') are unknown to the algorithm and are chosen by the adversary. our strategy is competitive with respect to the expected rejection ratio. more precisely, it achieves expected rejection ratio of at most r+epsilon, where r is the optimum expected rejection ratio. the expectations are taken over the distribution of the request sequences, and epsilon=sqrt(r log n), where r is the maximum fraction of an edge bandwidth that can be requested by a single circuit.
selection with monotone comparison cost. we consider the problem of selecting the rth-smallest element from a list of n elements under a model where the comparisons may have different costs depending on the elements being compared. this model was introduced by [3] and is realistic in the context of comparisons between complex objects. an important special case of this general cost model is one where the comparison costs are monotone in the sizes of the elements being compared. this monotone cost model covers most "natural" cost models that arise and the selection problem turns out to be the most challenging one among the usual problems for comparison-based algorithms. we present an o(log2 n)-competitive algorithm for selection under the monotone cost model. this is in contrast to an &omega;(n) lower bound that is known for arbitrary comparison costs. we also consider selection under a special case of monotone costs --- the min model where the cost of comparing two elements is the minimum of the sizes. we give a randomized o(1)-competitive algorithm for the min model.
computing the local consensus of trees. the inference of consensus from a set of evolutionary trees is a fundamental problem in a number of fields such as biology and historical linguistics, and many models for inferring this consensus have been proposed. in this paper we present a model for deriving what we call a local consensus tree t from a set of trees ${\cal t}$. the model we propose presumes a function f, called a total local consensus function, which determines for every triple a of species, the form that the local consensus tree should take on a. we show that all local consensus trees, when they exist, can be constructed in polynomial time and that many fundamental problems can be solved in linear time. we also consider partial local consensus functions and study optimization problems under this model. we present linear time algorithms for several variations. finally we point out that the local consensus approach ties together many previous approaches to constructing consensus trees.
reducing tile complexity for self-assembly through temperature programming. we consider the tile self-assembly model and how tile complexity can be eliminated by permitting the temperature of the self-assembly system to be adjusted throughout the assembly process. to do this, we propose novel techniques for designing tile sets that permit an arbitrary length m binary number to be encoded into a sequence of o(m) temperature changes such that the tile set uniquely assembles a supertile that precisely encodes the corresponding binary number. as an application, we show how this provides a general tile set of size o(1) that is capable of uniquely assembling essentially any n x n square, where the assembled square is determined by a temperature sequence of length o(log n) that encodes a binary description of n. this yields an important decrease in tile complexity from the required &omega;(log n/log log n) for almost all n when the temperature of the system is fixed. we further show that for almost all n, no tile system can simultaneously achieve both o(log n) temperature complexity and o(log n/log log n) tile complexity, showing that both versions of an optimal square building scheme have been discovered. this work suggests that temperature change can constitute a natural, dynamic method for providing input to self-assembly systems that is potentially superior to the current technique of designing large tile sets with specific inputs hardwired into the tileset.
on-line difference maximization. in this paper we examine problems motivated by on-line financial problems and stochastic games. in particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values.first, we consider a scenario in which only one low value and one high value may be selected. we give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n-o(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small---at most 15).in a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. we also give an optimal on-line algorithm for this problem, where the expected gain is $n^2/8-\theta(n\log n)$. an analysis shows that the optimal expected off-line gain is $n^2/6+\theta(1)$, so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy.
a comparison of labeling schemes for ancestor queries. motivated by a recent application in xml search engines we study the problem of labeling the nodes of a tree (xml file) such that given the labels of two nodes one can determine whether one node is an ancestor of the other. we describe several new prefix-based labeling schemes, where an ancestor query roughly amounts to testing whether one label is a prefix of the other. we compare our new schemes to a simple interval-based scheme currently used by search engines, as well as, to schemes with the best theoretical guarantee on the maximum label length. we performed our experimental evaluation on real xml data and on some families of random trees.