waashk/dblp huggingface dataset:
fully polynomial time approximation schemes for stochastic dynamic programs. we develop a framework for obtaining (deterministic) fully polynomial time approximation schemes (fptass) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. using our framework, we give the first fptass for several np-hard problems in various fields of research such as knapsack-related problems, logistics, operations management, economics, and mathematical finance.
charity auctions on social networks. charitable giving is influenced by many social, psychological, and economic factors. one common way to encourage individuals to donate to charities is by offering to match their contribution (often by their employer or by the government). conitzer and sandholm introduced the idea of using auctions to allow individuals to offer to match the contribution of others. we explore this idea in a social network setting, where individuals care about the contribution of their neighbors, and are allowed to specify contributions that are conditional on the contribution of their neighbors. we give a mechanism for this setting that raises the largest individually rational contributions given the conditional bids, and analyze the equilibria of this mechanism in the case of linear utilities. we show that if the social network is strongly connected, the mechanism always has an equilibrium that raises the maximum total contribution (which is the contribution computed according to the true utilities); in other words, the price of stability of the game defined by this mechanism is one. interestingly, although the mechanism is not dominant strategy truthful (and in fact, truthful reporting need not even be a nash equilibrium of this game), this result shows that the mechanism always has a full-information equilibrium which achieves the same outcome as in the truthful scenario. of course, there exist cases where the maximum total contribution even with true utilities is zero: we show that the existence of non-zero equilibria can be characterized exactly in terms of the largest eigenvalue of the utility matrix associated with the social network.
cutting cycles of rods in space: hardness and approximation. we study the problem of cutting a set of rods (line segments in ℝ3) into fragments, using a minimum number of cuts, so that the resulting set of fragments admits a depth order. we prove that this problem is np-complete, even when the rods have only three distinct orientations. we also give a polynomial-time approximation algorithm with no restriction on rod orientation that computes a solution of size o(&tau; log &tau; log log &tau;), where &tau; is the size of an optimal solution.
improved algorithms for orienteering and related problems. in this paper we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. the point to point-orienteering-problem is the following: given an edge-weighted graph g = (v, e) (directed or undirected), two nodes s, t &isin; v and a budget b, find an s-t walk in g of total length at most b that maximizes the number of distinct nodes visited by the walk. this problem is closely related to tour problems such as tsp as well as network design problems such as k-mst. our main results are the following. &bull; a 2 + &epsilon; approximation in undirected graphs, improving upon the 3-approximation from [6]. &bull; an o(log2 opt) approximation in directed graphs. previously, only a quasi-polynomial time algorithm achieved a poly-logarithmic approximation [14] (a ratio of o (log opt)). the above results are based on, or lead to, improved algorithms for several other related problems.
minimizing average latency in oblivious routing. we consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. this is roughly equivalent to minimizing the function &sigma;e(load(e))2, where for a network link e, load(e) denotes the amount of traffic that has to be forwarded by the link. we show that for the case when all routing requests are directed to a single target, there is a routing scheme with competitive ratio o(log n, where n denotes the number of nodes in the network. as a lower bound we show that no oblivious scheme can obtain a competitive ratio of better than &omega;(&radic;log n). this latter result gives a qualitative difference in the performance that can be achieved by oblivious algorithms and by adaptive online algorithms, respectively, since there exist a constant competitive online routing algorithm for the cost-measure of average latency [2]. such a qualitative difference (in general undirected networks) between the performance of online algorithms and oblivious algorithms was not known for other cost measures (e.g. edge-congestion).
the effect of induced subgraphs on quasi-randomness. one of the main questins that arise when studying random and quasi-random structures is which properties p are such that any object that satisfies p "behaves" like a truly random one. in the context of graphs, chung, graham, and wilson [9] call a graph p-quasi-random if it satisfies a long list of the properties that hold in g(n, p) with high probability, like edge distribution, spectral gap, cut size, and more. our main result here is that the following holds for any fixed graph h: if the distribution of induced copies of h in a graph g is close (in a well defined way) to the distribuition we would expect to have in g(n,p), then g is either p-quasi-random or p-quasirandom, where &pmacr; is the unique non-trivial solution of the polynomial equation x&delta; (1 -- x)1-&delta; = p&delta; (1 -- p)1--&delta;, with &delta; being the edge density of h. we thus infer that having the correct distribution of induced copies of any single graph h, is enough to guarantee that a graph has the properties of a random one. the proof techniques we develop here, which combine probabilistic, algebraic and combinatorial tools, may be of independent interest to the study of quasi-random structures.
lower-bounded facility location. we study the lower-bounded facility location problem, which generalizes the classical uncapacitated facility location problem in that it comes with lower bound constraints for the number of clients assigned to a facility in the case that this facility is opened. this problem was introduced independently in the papers by karger and minkoff [12] and by guha, meyerson, and munagala [7], both of which give bicriteria approximation algorithms for it. these bicriteria algorithms come within a constant factor of the optimal solution cost, but they also violate the lower bound constraints by a constant factor. our result in this paper is the first true approximation algorithm for the lower-bounded facility location problem, which respects the lower bound constraints and achieves a constant approximation ratio for the objective function. the main technical idea for the design of the algorithm is a reduction to the capacitated facility location problem, which has known constant-factor approximation algorithms.
adaptive local ratio. local ratio is a well-known paradigm for designing approximation algorithms for combinatorial optimization problems. at a very high level, a local ratio algorithm first decomposes the input weight function w into a positive linear combination of simpler weight functions or models. guided by this process a solution s is constructed such that s is &alpha;-approximate with respect to each model used in the decomposition. as a result, s is &alpha;-approximate under w as well. these models usually have a very simple structure that remains "unchanged" throughout the execution of the algorithm. in this work we show that adaptively choosing a model from a richer spectrum of functions can lead to a better local ratio. indeed, by turning the search for a good model into an optimization problem of its own, we get improved approximations for a data migration problem.
deterministic random walks on regular trees. jim propp's rotor router model is a deterministic analogue of a random walk on a graph. instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. cooper and spencer (comb. probab. comput. (2006)) show a remarkable similarity of both models. if an (almost) arbitrary population of chips is placed on the vertices of a grid zd and does a simultaneous walk in the propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. this constant is independent of the starting configuration and the order in which each vertex serves its neighbors. this result raises the question if all graphs do have this property. with quite some effort, we are now able to answer this question negatively. for the graph being an infinite k-ary tree (k &ge; 3), we show that for any deviation d there is an initial configuration of chips such that after running the propp model for a certain time there is a vertex with at least d more chips than expected in the random walk model. however, to achieve a deviation of d it is necessary that at least k&theta;(d) vertices contribute by being occupied by a number of chips not divisible by k in a certain time interval.
iterated rounding algorithms for the smallest -edge connected spanning subgraph. we present the best known algorithms for approximating the minimum cardinality undirected k-edge connected spanning subgraph. for simple graphs our approximation ratio is 1 + 1/2k + o(1/k2). the more precise version of our bound requires k &ge; 7, and for all such k it improves the longstanding bound of cheriyan and thurimella, 1 + 2/(k + 1) [2]. the improvement comes in two steps: first we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound (n(1 + 3/k + o(1/k&radic;k)) versus 2n). this immediately implies that iterated rounding improves the bound of [2]. our second step improves iterated rounding by finding good edges for rounding. for multigraphs our approximation ratio is 1 + 21/11k < 1 + 1.91/k. this improves the previous bound 1 + 2/k [6]. it is of interest since it is known that for some constant c > 0, an approximation ratio &le; 1 + c/k implies p = np. our approximation ratio extends to the minimum cardinality steiner network problem, where k denotes the average vertex demand. the algorithm exploits rounding properties of the first two linear programs in iterated rounding.
a local algorithm for finding dense subgraphs. a local graph algorithm is one that searches for an approximation of the best solution near a specified starting vertex, and has a running time independent of the size of the graph. recently, local algorithms have been developed for graph partitioning and clustering. in this paper, we present a local algorithm for finding dense subgraphs of bipartite graphs, according to the measure of density proposed by kannan and vinay. the algorithm takes as input a bipartite graph with a specified starting vertex, and attempts to find a dense subgraph near that vertex. we prove the following local approximation guarantee for the algorithm. for any subgraph s with k vertices and density &theta;, there is a large set of starting vertices within s for which the algorithm produces a subgraph with density &omega;(&theta;/log &delta;), where &delta; is the maximum degree. the running time of the algorithm is o(&delta;k2), independent of the number of vertices in the graph.
optimal universal graphs with deterministic embedding. let h be a finite family of graphs. a graph g is h-universal if it contains a copy of each h &isin; h as a subgraph. let h(k,n) denote the family of graphs on n vertices with maximum degree at most k. for all admissible k and n, we construct an h(k, n)-universal graph g with at most ckn2-2/k edges, where ck is a constant depending only on k. this is optimal, up to the constant factor ck, as it is known that c'kn2-2/k is a lower bound for the number of edges in any such graph. the construction of g is explicit, and there is an efficient deterministic algorithm for finding a copy of any given h &isin; h(k,n) in g.
approximating tsp on metrics with bounded global growth. the traveling salesman problem (tsp) is a canonical np-complete problem which is known to be max-snp hard even on (high-dimensional) euclidean metrics [39]. in order to circumvent this hardness, researchers have been developing approximation schemes for low-dimensional metrics [4, 38] (under different notions of dimension). however, a feature of most current notions of metric dimension is that they are "local": the definitions require every local neighborhood to be well-behaved. in this paper, we consider the case when the metric is less restricted: it has a few "dense" regions, but is "well-behaved on the average"? to this end, we define a global notion of dimension which we call the correlation dimension (denoted by dimc), which generalizes the popular notion of doubling dimension. in fact, the class of metrics with dimc = o(1) not only contains all doubling metrics, but also contains some metrics containing uniform submetrics of size &radic;n. we first show, using a somewhat "local" argument, that one can solve tsp on these metrics in time 2o(&radic;n); we then take advantage of the global nature of tsp (and the global nature of our definition) to give a (1 + &epsilon;)-approximation algorithm that runs in sub-exponential time: i.e., in 2o(n&delta;&epsilon;-4dimc)-time for every constant 0 < &delta; < 1.
geometric and topological guarantees for the wrap reconstruction algorithm. we describe a variant of edelsbrunner's wrap algorithm for surface reconstruction, for which we can prove geometric and topological guarantees within the &epsilon;-sampling model. the wrap algorithm is based on ideas from morse theory applied to the flow map induced by certain distance function. the variant is made possible by a previous result on the "separation" of critical points for a related distance function that directly applies in this case. though the variant is easily proposed, in order to prove the quality guarantees for the output, we need to closely investigate the geometric properties of the flow map.
on bounded leg shortest paths problems. let v be a set of points in a d-dimensional lp-metric space. let s, t &epsilon; v and let l be any real number. an l-bounded leg path from s to t is an ordered set of points which connects s to t such that the leg between any two consecutive points in the set is at most l. the minimal path among all these paths is the l-bounded leg shortest path from s to t. in the s-t bounded leg shortest path (stblsp) problem we are given two points s and t and a real number l, and are required to compute an l-bounded leg shortest path from s to t. in the all-pairs bounded leg shortest path (apblsp) problem we are required to build a data structure that, given any two query points from v and any real number l, outputs the length of the l-bounded leg shortest path (a distance query) or the path itself (a path query). in this paper present first an algorithm for the apblsp problem in any lp-metric which, for any fixed &epsilon; > 0, computes in o(n3 n = log2 n &middot; &epsilon;-d)) time a data structure which approximates any bounded leg shortest path within a multiplicative error of (1 + &epsilon;). it requires o(n2log n) space and distance queries are answered in o (log log n) time. this improves on an algorithm with running time of o(n5) given by bose et al. in [8]. we present also an algorithm for the stblsp problem that, given s, t &isin; v and a real number l, computes in o(n &middot; polylog(n)) the exact l-bounded shortest path from s to t. this algorithm works in l1 and l&infin; metrics. in the euclidean metric we also obtain an exact algorithm but with a running time of o(n4/3+&epsilon;), for any &epsilon; > 0. we end by showing that for any weighted directed graph there is a data structure of size o(n2.5log n) which is capable of answering path queries with a multiplicative error of (1 + &epsilon;) in o (log log n + &ell;) time, where &ell; is the length of the reported path. our results improve upon the results given by bose et al. [8]. our algorithms incorporate several new ideas along with an interesting observation made on geometric spanners, which is of an independent interest.
faster dynamic matchings and vertex connectivity. we present first fully dynamic subquadratic algorithms for: computing maximum matching size, computing maximum bipartite matching weight, computing maximum number of vertex disjoint s, t paths and testing directed vertex k-connectivity of the graph. the presented algorithms are randomized. the algorithms for maximum matching size and disjoint paths support operations in o(n1.495) time. the algorithm for computing the maximum bipartite matching weight maintains the graph with integer edge weights from the set 1,..., w in o(w2.495n1.495) time. the algorithm for testing directed vertex k-connectivity supports updates in o(n1.575 + nk2) time. for all of these problems the presented dynamic algorithms break the input size barrier --- o(n2). as a side result we obtain a dynamic algorithm for the dynamic maintenance of the rank of the matrix that support updates in o(n1.495) time.
yet another algorithm for dense max cut: go greedy. we study dense instances of maxcut and its generalizations. following a long list of existing, diverse and often sophisticated approximation schemes, we propose taking the na&iuml;ve greedy approach; we prove that when the vertices are considered in random order, our algorithms are still approximation schemes. our algorithms may be simple, but the analysis is not. it relies on smoothing the vertices defining the partial cuts and on proving certain martingale properties. we also give a simpler proof of the result from alon, fernandez de la vega, kannan, and karpinski [1] that dense problems have sample complexity &otilde; (1/&epsilon;4). like previous work, our results generalize to dense maximum constraint satisfaction problems.
approximation algorithms for stochastic and risk-averse optimization. we present improved approximation algorithms in stochastic optimization. we prove that the multi-stage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same approximation algorithms as their standard (non-stochastic) counterparts; this improves upon work of swamy & shmoys that shows an approximability which depends multiplicatively on the number of stages. we also present approximation algorithms for facility location and some of its variants in the 2-stage recourse model, improving on previous approximation guarantees.
the effectiveness of stackelberg strategies and tolls for network congestion games. it is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal centralized solution may be unbounded even if the system consists of only two parallel links. this ratio is called the price of anarchy (poa). in this paper, we investigate ways by which one can reduce the performance degradation due to selfish behavior. we investigate two primary methods (a) stackelberg routing strategies, where a central authority, e.g., network manager, controls a fixed fraction of the flow, and can route this flow in any desired way so as to influence the flow of selfish users; and (b) network tolls, where tolls are imposed on the edges to modify the latencies of the edges, and thereby influence the induced nash equilibrium. we obtain results demonstrating the effectiveness of both stackelberg strategies and tolls in controlling the price of anarchy. for stackelberg strategies, we obtain the first results for nonatomic routing in graphs more general than parallel-link graphs, and strengthen existing results for parallel-link graphs, (i) in series-parallel graphs, we show that stackelberg routing reduces the poa to a constant (depending on the fraction of flow controlled). (ii) for general graphs, we obtain latency-class specific bounds on the poa with stackelberg routing, which give a continuous trade-off between the fraction of flow controlled and the price of anarchy, (iii) in parallel-link graphs, we show that for any given class l of latency functions, stackelberg routing reduces the poa to at most &alpha; + (1 - &alpha;) &middot; &rho;(l), where &alpha; is the fraction of flow controlled and &rho;(l) is the poa of class l (when &alpha; = 0). for network tolls, motivated by the known strong results for nonatomic games, we consider the more general setting of atomic splittable routing games. we show that tolls inducing an optimal flow always exist, even for general asymmetric games with heterogeneous users, and can be computed efficiently by solving a convex program. furthermore, we give a complete characterization of flows that can be induced via tolls. these are the first results on the effectiveness of tolls for atomic splittable games.
lower bounds on average-case delay for video-on-demand broadcast protocols. video-on-demand broadcast protocols are commonly used to deliver video content to a large uncoordinated set of consumers. since broadcast protocols are not attuned to individual user requests, some delay in service is unavoidable. the worst-case delay, expressed as a function of the available bandwidth, has been well studied; matching upper and lower bounds have been established in a very general setting. in this paper we turn our attention to average-case delay. we establish asymptotically tight lower bounds on average-case delay in the situation where receiver and sender bandwidths are equal. it follows from our results that existing worst-case-optimal broadcast protocols are, to within a small constant factor, optimal in the average case as well.
matrix-vector multiplication in sub-quadratic time: (some preprocessing required). we show that any n x n matrix a over any finite semiring can be preprocessed in o(n2+&epsilon;) time, such that all subsequent vector multiplications with a can be performed in o(n2/(&epsilon;logn)2) time, for all &epsilon; > 0. the approach is combinatorial and can be implemented on a pointer machine or a (logn)-word ram. some applications are described.
maximum matching in graphs with an excluded minor. we present a new randomized algorithm for finding a maximum matching in h-minor free graphs. for every fixed h, our algorithm runs in o(n3&omega;/(&omega;+3)) < o(n1.326) time, where n is the number of vertices of the input graph and &omega; < 2.376 is the exponent of matrix multiplication. this improves upon the previous o(n1.5) time bound obtained by applying the o(mn1/2)-time algorithm of micali and vazirani on this important class of graphs. for graphs with bounded genus, which are special cases of h-minor free graphs, we present a randomized algorithm for finding a maximum matching in o(n&omega;/2) < o(n1.19) time. this extends a previous randomized algorithm of mucha and sankowski, having the same running time, that finds a maximum matching in a planar graphs. we also present a deterministic algorithm with a running time of o(n1+&omega;/2) < o(n2.19) for counting the number of perfect matchings in graphs with bounded genus. this algorithm combines the techniques used by the algorithms above with the counting technique of kasteleyn. using this algorithm we can also count, within the same running time, the number of t-joins in planar graphs. as special cases, we get algorithms for counting eulerian subgraphs (t = &phis;) and odd subgraphs (t = v) of planar graphs.