waashk/dblp huggingface dataset:
computing equilibria for congestion games with (im)perfect information. we study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. each customer has a particular demand of service and the behavior of the customers is determined by utility functions that are non-increasing in the congestion. customers decide whether to join or leave the service based on the experienced congestion and the offered prices. following standard game theory, we assume each customer behaves in the most rational way. if the prices of service are fixed, then such a customer behavior leads to a pure, not necessarily unique nash equilibrium among the customers. in order to evaluate marketing strategies, the service provider is interested in estimating its revenue under the best and worst customer equilibria. we study the complexity of this problem under different models of information available to the provider.&bull;we first consider the classical model in which the provider has perfect knowledge of the behavior of all customers. we present a complete characterization of the complexity of computing optimal pricing strategies and of computing best and worst equilibria. basically, we show that most of these problems are inapproximable in the worst case but admit an "average-case fpas." our average case analysis covers general distributions for customer demands and utility thresholds. we generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.&bull;we extend our analysis to a more realistic model in which the provider has incomplete information. following the game theoretic framework of bayesian games introduced by harsanyi, we assume that the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best and worst equilibria. somewhat counterintuitive, we obtain an fpras for the equilibria problem in the model with imperfect information although the problem with perfect information is inapproximable under the worst case measures. in particular, the worst case complexity of the considered stochastic equilibria problems increases with the precision of the available knowledge.
probabilistic analysis of knapsack core algorithms. we study the average-case performance of algorithms for the binary knapsack problem. our focus lies on the analysis of so-called core algorithms, the predominant algorithmic concept used in practice. these algorithms start with the computation of an optimal fractional solution that has only one fractional item and then they exchange items until an optimal integral solution is found. the idea is that in many cases the optimal integral solution should be close to the fractional one such that only a few items need to be exchanged. despite the well known hardness of the knapsack problem on worst-case instances, practical studies show that knapsack core algorithms can solve large scale instances very efficiently. for example, they exhibit almost linear running time on purely random inputs.in this paper, we present the first theoretical result on the running time of core algorithms that comes close to the results observed in practical experiments. we prove an upper bound of o(npolylog(n)) on the expected running time of a core algorithm on instances with n items whose profits and weights are drawn independently, uniformly at random. a previous analysis on the average-case complexity of the knapsack problem proves a running time of o(n4), but for a different kind of algorithms. the previously best known upper bound on the running time of core algorithms is polynomial as well. the degree of this polynomial, however, is at least a large three digit number. in addition to uniformly random instances, we investigate harder instances in which profits and weights are pairwise correlated. for this kind of instances, we can prove a tradeoff describing how the degree of correlation influences the running time.
the knuth-yao quadrangle-inequality speedup is a consequence of total-monotonicity. there exist several general techniques in the literature for speeding up naive implementations of dynamic programming. two of the best known are the knuth-yao quadrangle inequality speedup and the smawk algorithm for finding the row-minima of totally monotone matrices. although both of these techniques use a quadrangle inequality and seem similar, they are actually quite different and have been used differently in the literature. in this article we show that the knuth-yao technique is actually a direct consequence of total monotonicity. as well as providing new derivations of the knuth-yao result, this also permits to solve the knuth-yao problem directly using the smawk algorithm. another consequence of this approach is a method for solving online versions of problems with the knuth-yao property. the online algorithms given here are asymptotically as fast as the best previously known static ones. for example, the knuth-yao technique speeds up the standard dynamic program for finding the optimal binary search tree of n elements from &theta;(n3) down to o(n2), and the results in this article allow construction of an optimal binary search tree in an online fashion (adding a node to the left or the right of the current nodes at each step) in o(n) time per step.
a constant-factor approximation algorithm for optimal terrain guarding. we present the first constant-factor approximation algorithm for a non-trivial instance of the optimal guarding (coverage) problem in polygons. in particular, we give an o(1)-approximation algorithm for placing the fewest point guards on a 1.5d terrain, so that every point of the terrain is seen by at least one guard. while polylogarithmic-factor approximations follow from set cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.
a locality-preserving cache-oblivious dynamic dictionary. this paper presents a simple dictionary structure designed for a hierarchical memory. the proposed data structure is cache-oblivious and locality-preserving. a cache-oblivious data structure has memory performance optimized for all levels of the memory hierarchy even though it has no memory-hierarchy-specific parameterization. a locality-preserving dictionary maintains elements of similar key values stored close together for fast access to ranges of data with consecutive keys.the data structure presented here is a simplification of the cache-oblivious b-tree of bender, demaine, and farach-colton. the structure supports search operations on n data items using o(logb n + 1) block transfers at a level of the memory hierarchy with block size b. insertion and deletion operations use o(logbn + log2 n/b + 1) amortized block transfers. finally, the data structure returns all k data items in a given search range using o(logb n + k/b + 1) block transfers.this data structure was implemented and its performance was evaluated on a simulated memory hierarchy. this paper presents the results of this simulation for various combinations of block and memory sizes.
improved bounds on sorting with length-weighted reversals. we study the problem of sorting integer sequences and permutations by length-weighted reversals. we consider a wide class of cost functions, namely f(l) = l&alpha; for all &alpha; &ge; 0, where l is the length of the reversed subsequence. we present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. then we develop algorithms to approximate the optimal cost to sort a given input. furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. our results have direct application in computational biology to the field of comparative genomics.
improved algorithms for stretch scheduling. we study the basic problem of preemptive scheduling of an online stream of jobs on a single processor. the ith job arrives at time r(i) and has processing time p(i) that is known at the time of its arrival. if c(i) is the completion time of job i, then the flow time is c(i) - r(i) and stretch of a job is the ratio of its flow time to its processing time; that is, c(i)-r(i)/p(i). flow time considers the time a job is in the system regardless of the service it requested; the stretch measure relies on the intuition that a job that requested long service must be prepared to wait longer than the small jobs.in this paper, we present improved algorithmic results in stretch scheduling. we first show that a simple online algorithm that takes amortized o(1) time per job arrival is o(&delta;1/2)-competitive with respect to maximum stretch, where &delta; is the ratio of the largest processing time to the smallest processing time. this is significantly more efficient than the best known online algorithm for this problem which takes &omega;(n2) per scheduling step (n is the number of jobs seen thus far). we next present a polynomial time approximation scheme for average stretch scheduling. the previous best polynomial-time algorithm is the shortest remaining processing time algorithm, which achieves a 2-approximation. finally, we consider the impact of incomplete knowledge of job sizes on the average stretch performance of scheduling algorithms. we show that a constant-factor competitive ratio for average stretch is achievable even if the processing times (or remaining processing times) of jobs are known only to within a constant factor of accuracy.
distributed selfish load balancing. suppose that a set of $m$ tasks are to be shared as equally as possible among a set of $n$ resources. a game-theoretic mechanism to find a suitable allocation is to associate each task with a &ldquo;selfish agent&rdquo; and require each agent to select a resource, with the cost of a resource being the number of agents that select it. agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced. recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control. in this paper we discuss a natural protocol for the agents which combines the following desirable features: it can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. for $m \gg n$, the system becomes approximately balanced (an $\epsilon$-nash equilibrium) in expected time $o(\log \log m)$. we show using a martingale technique that the process converges to a perfectly balanced allocation in expected time $o(\log \log m + n^4)$. we also give a lower bound of $\omega(\max\{\log \log m, n\})$ for the convergence time.
vertical ray shooting and computing depth orders for fat objects. we present new results for three problems dealing with a set p of n convex constant-complexity fat polyhedra in 3-space. (i) we describe a data structure for vertical ray shooting in p that has o(log2 n) query time and uses o(n log2 n) storage. (ii) we give an algorithm to compute in o(n log3 n) time a depth order on p, if it exists. (iii) we give an algorithm to verify in o(n log4 n) time whether a given order on p is a valid depth order. all three results improve on previous results.
the fourth moment method. higher moment analysis has typically been used to upper bound certain functions. in this paper, we introduce a new combinatorial method to lower bound the expectation of the absolute value of a random variable x by the expectation of a quartic in x. in the special case where we are looking at the absolute value of a (weighted) sum of {-1,+1} unbiased random variables, we achieve tight bounds, using only a fourth moment, for the total discrepancy of a set system. because the fourth moment depends only on 4-wise independence, our bounds will hold over polynomially sized distributions, and so these bounds will be directly applicable in removing randomness to obtain nc algorithms. we obtain the first nc algorithms for the problems of total discrepancy, maximum acyclic subgraph, tournament ranking, the gale--berlekamp switching game, and edge discrepancy. we show that for most of these applications it is truly necessary to consider a fourth moment by exhibiting a 3-wise independent distribution which does not achieve the required bounds. our method is strong enough to give a new combinatorial bound on tournament ranking.
on the spread of viruses on the internet. we analyze the contact process on random graphs generated according to the preferential attachment scheme as a model for the spread of viruses in the internet. we show that any virus with a positive rate of spread from a node to its neighbors has a non-vanishing chance of becoming epidemic. quantitatively, we discover an interesting dichotomy: for a virus with effective spread rate &lambda;, if the infection starts at a typical vertex, then it develops into an epidemic with probability &lambda;&theta;(log(1/&lambda;)/log log(1/&lambda;), but on average the epidemic probability is &lambda;&theta;(1).
efficient dynamic traitor tracing. the notion of traitor tracing was introduced by chor, fiat, and naor [tracing traitors, lecture notes in comput. sci. 839, 1994, pp. 257--270] in order to combat piracy scenarios. recently, fiat and tassa [ tracing traitors, lecture notes in comput. sci. 1666, 1999, pp. 354--371] proposed a dynamic traitor tracing scenario, in which the algorithm adapts dynamically according to the responses of the pirate. let n be the number of users and p the number of traitors.our main result is an algorithm which locates p traitors, even if p is unknown, using a watermarking alphabet of size p+1 and an optimal number of $\theta(p^2 + p\log n)$ rounds. this improves the exponential number of rounds achieved by fiat and tassa in this case. we also present two algorithms that use a larger alphabet: for an alphabet of size p+c+1, $c\geq1$, an algorithm that uses o(p2/c+ p log n) rounds; for an alphabet of size pc+1, an algorithm that uses o(p logcn) rounds.our final result is a lower bound of $\omega(p^2/c+p\log_{c+1}n)$ rounds for any algorithm that uses an alphabet of size p+c, assuming that p is not known in advance.
slice and dice: a simple, improved approximate tiling recipe. we are given a two dimensional array a[1 &sdot;&sdot;&sdot; n, 1 &sdot;&sdot;&sdot; n] where each a[i, j] stores a non-negative number. a (rectangular) tiling of a is a collection of rectangular portions a[l &sdot;&sdot;&sdot; r, t &sdot;&sdot;&sdot; b], called tiles, such that no two tiles overlap and each entry a[i, j] is contained in a tile. the weight of a tile is the sum of all array entries in it.in the max-min problem, we are given a weight bound w and our goal is to find a tiling such that (a) each tile is of weight at least w (the min condition) and (b) the number of tiles is maximized (the max condition). in the min-max problem, we are given a weight bound w again and our goal is to find a tiling such that (a) each tile has weight at most w and (b) the number of tiles is minimized. these two basic problems have many variations depending on the weight functions, whether some areas of a must not be covered, or whether some portion of a may be discarded, etc. these problems are not only natural combinatorial problems, but also arise in a plethora of applications, e.g., in databases and data mining, video compression, load balancing, building index structures, manufacturing and so forth.both the above tiling problems (as well as all of their variations relevant to this paper) are known to be np-hard. in this paper, we present approximations algorithms for solving these problems based on epicurean methods : variations of a basic slice-and-dice technique. surprisingly, these simple algorithms yield small constant factor approximations for all these problems. for some of the problems, our results are the first known approximations; for others, our results improve the known algorithms significantly in approximation bounds and/or running time. of independent interest are the tight bounds we show for sizes of the binary space partition trees for isothetic rectangles.
improved approximation algorithms for rectangle tiling and packing. we provide improved approximation algorithms for several rectangle tiling and packing problems (rtile, drtile and d-rpack) studied in the literature. our algorithms are highly efficient since their running times are near-linear in the space input size rather than in the domain size. in addition, we improve the best known approximation ratios, in some cases quite significantly.
approximating minimum unsatisfiability of linear equations. we consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the minimized objective function is the number of equations that are not satisfied. for the case of the finite field gf[2], this problem is also known as the nearest codeword problem. in this note we show that for any constant c there exists a randomized polynomial time algorithm that approximates the above problem, called the minimum unsatisfiability of linear equations (min-unsatisfy for short), with n/(c log n) approximation ratio. our results hold for any field in which systems of linear equations can be solved in polynomial time.
optimizing misdirection. in this paper we consider the following problem. given a (d + 1)-claw free graph g = (v, e, w) where w : v &rarr; r+, maximize w(a) where a is an independent set in g. our focus is to minimize the approximation ratio (optimum/obtained) in polynomial time that does not depend on d. our approach is to apply local improvements of size 2, using a "misdirected" criterion, i.e. w&alpha;(a) rather than w(a). we find the optimal value of &alpha; for every d, and the resulting ratio is roughly 0.667d for d = 3, 0.651d for d = 4 and 0.646d for d > 4.
8/7-approximation algorithm for (1, 2)-tsp. we design a polynomial time 8/7-approximation algorithm for the traveling salesman problem in which all distances are either one or two. this improves over the best known approximation factor for that problem. as a direct application we get a 7/6-approximation algorithm for the maximum path cover problem, similarly improving upon the best known approximation factor for that problem. the result depends on a new method of consecutive path cover improvements and on a new analysis of certain related color alternating paths. this method could be of independent interest.
improved approximations for the steiner tree problem. for a set s contained in a metric space, a steiner tree of s is a tree that connects the points in s. finding a minimum cost steiner tree is an np-hard problem in euclidean and rectilinear metrics as well as in graphs. we give an approximation algorithm and show that the worst-case ratio of the cost of our solutions to the optimal cost is better than previously known ratios in graphs, and in rectilinear metric on the plane. our method offers a trade-off between the running time and the ratio; on one hand it always allows to improve the ratio, on the other it allows to obtain previously known ratios with much greater efficiency. we use properties of optimal rectilinear steiner trees to obtain significantly better ratio and running time in rectilinear metric.
computing the depth of a flat. we compute the regression depth of a k-flat in a set of n points in rd, in time &ogr;(nd-2 + n log n) for 1 &lne; k &lne; d - 2. this contrasts with a bound of &ogr;(nd-1 + n log n) when k = 0 or k = d - 1.
two tricks to triangulate chordal probe graphs in polynomial time. a graph g = (v,e) is chordal probe if its vertices can be partitioned into two sets p (probes) and n (non-probes) where n is a stable set and such that g can be extended to a chordal graph by adding edges between non-probes. the study of chordal probe graphs was originally motivated as a generalization of the interval probe graphs which occur in applications involving physical mapping of dna. however, chordal probe graphs also have their own computational biology application as a special case of constructing phylogenies, tree structures which model genetic mutations.we give several characterizations of chordal probe graphs, first in the case of a fixed given partition of the vertices into probes and non-probes, and second in the more general case where no partition is given. in both of these cases, our results are obtained by characterizing superclasses, namely, n-triangulatable graphs and cyclebicolorable graphs, which are first introduced here. we give polynomial time recognition algorithms for each class. the complexity is o (|p||e|), given a partition of the vertices into probes and non-probes, thus also providing a interesting tractible subcase of the chordal graph sandwich problem. if no partition is given in advance, the complexity of our recognition algorithm is o(|v|2|e|).
from valid inequalities to heuristics: a unified view of primal-dual approximation algorithms in covering problems. in recent years approximation algorithms based on primal-dual methods have been successfully applied to a broad class of discrete optimization problems. in this paper, we propose a generic primal-dual framework to design and analyze approximation algorithms for integer programming problems of the covering type that uses valid inequalities in its design. the worst-case bound of the proposed algorithm is related to a fundamental relationship (called strength) between the set of valid inequalities and the set of minimal solutions to the covering problems. in this way, we can construct an approximation algorithm simply by constructing the required valid inequalities. we apply the proposed algorithm to several problems, such as covering problems related to totally balanced matrices, cyclic scheduling, vertex cover, general set covering, intersections of polymatroids, and several network design problems attaining (in most cases) the best worst-case bound known in the literature.
computing homotopic shortest paths in the plane. we address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. problems on homotopy of paths received attention very recently [cabello et al., in: proc. 18th annu. acm sympos. comput. geom., 2002, pp. 160-169; efrat et al., in: proc. 10th annu. european sympos. algorithms, 2002, pp. 411-423]. we present two output-sensitive algorithms, for simple paths and non-simple paths. the algorithm for simple paths improves the previous algorithm [efrat et al., in: proc. 10th annu. european sympos. algorithms, 2002, pp. 411-423]. the algorithm for non-simple paths achieves o(log2n) time per output vertex which is an improvement by a factor of o(n/log2n) of the previous algorithm [hershberger, snoeyink, comput. geom. theory appl. 4 (1994) 63-98], where n is the number of obstacles. the running time has an overhead o(n2+ε) for any positive constant ε. in the case k < n2+ε, where k is the total size of the input and output, we improve the running to o((n + k + (nk)2/3) logo(1) n).
sampling binary contingency tables with a greedy start. we study the problem of counting and randomly sampling binary contingency tables. for given row and column sums, we are interested in approximately counting (or sampling) 0/1 n x m matrices with the specified row/column sums. we present a simulated annealing algorithm with running time o((nm)2d3dmaxlog5(n+m)) for any row/column sums where d is the number of non-zero entries and dmax is the maximum row/column sum. this is the first algorithm to directly solve binary contingency tables for all row/column sums. previous work reduced the problem to the permanent, or restricted attention to row/column sums that are close to regular. the interesting aspect of our simulated annealing algorithm is that it starts at a non-trivial instance, whose solution relies on the existence of short alternating paths in the graph constructed by a particular greedy algorithm.