The proceedings contain 133 papers. The topics discussed include: an improved competitive algorithm for reordering buffer management;how to meet asynchronously (almost) everywhere;towards the randomized k-server conje...
ISBN:
(纸本)9780898717013
The proceedings contain 133 papers. The topics discussed include: an improved competitive algorithm for reordering buffer management;how to meet asynchronously (almost) everywhere;towards the randomized k-server conjecture: a primal-dual approach;property testing and parameter testing for permutations;on the cell probe complexity of dynamic membership;decomposition, approximation, and coloring of odd-minor-free graphs;the edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs;an (almost) linear time algorithm for odd cycles transversal;a quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing;asymmetric traveling salesman path and directed latency problems;compact ancestry labeling schemes for XML trees;algorithms for ray class groups and Hilbert class fields;data structures for range minimum queries in multidimensional arrays;and counting inversions, offline orthogonal range counting, and related problems.
The proceedings contain 54 papers. The topics discussed include: maintenance of a minimum spanning forest in a dynamic planar graph;incremental algorithms for minimal length paths;a data structure for arc insertion an...
ISBN:
(纸本)0898712513
The proceedings contain 54 papers. The topics discussed include: maintenance of a minimum spanning forest in a dynamic planar graph;incremental algorithms for minimal length paths;a data structure for arc insertion and regular path finding;incremental evaluation of computational circuits;multilevel adaptive hashing;new techniques for the union-find problem;efficient maintenance of the union intervals on a line, with applications;new techniques for some dynamic closest-point and farthest-point problems;and experiments an traveling salesman heuristics.
The proceedings contain 181 papers. The topics discussed include: an almost 2-approximation for all-pairs of shortest paths in subquadratic time;truly subcubic min-plus product for less structured matrices, with appli...
ISBN:
(纸本)9781611975994
The proceedings contain 181 papers. The topics discussed include: an almost 2-approximation for all-pairs of shortest paths in subquadratic time;truly subcubic min-plus product for less structured matrices, with applications;equivalences between triangle and range query problems;new algorithms and lower bounds for all-pairs max-flow in undirected graphs;tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem);learning from satisfying assignments under continuous distributions;a tight analysis of greedy yields subexponential time approximation for uniform decision tree;and nearly optimal edge estimation with independent set queries.
Spectral methods lid ye been widely used in a broad range of applications fields One important, object. involved in such methods is the Laplace-Beltrami operator of a manifold. Indeed, a variety of work in graphics an...
详细信息
ISBN:
(纸本)9780898717013
Spectral methods lid ye been widely used in a broad range of applications fields One important, object. involved in such methods is the Laplace-Beltrami operator of a manifold. Indeed, a variety of work in graphics and geometric optimization uses the eigen-structures (i.e, the eigenvalues and eigenfunctions) of the Laplace operator Applications include mesh smoothing, compression, editing, shape segmentation, matching parameterization, and so on While the Laplace, operator is defined (mathematically) for a smooth domain, these applications often approximate a smooth manifold by a disci etc mesh The spectral structure of the manifold Laplacian is estimated from some discrete Laplace operator constructed horn this mesh In this paper, we study the important, question of how well the spectrum computed horn the disci etc mesh approximates the true spectrum of the manifold Laplacian We exploit. a recent. result CM mesh Laplacian and provide the first convergence result to elate the spectrum constructed from a general mesh (approximating an m-manifold embedded in R-d) with the true spectrum We also study how stable these eigenvalues and their discrete approximations are when the underlying manifold is per tin bed, and provide explicit bounds for the Laplacian spectra a of two "close" manifolds. as well as a convergence result for their discrete approximations Finally, we present, vat ions experimental results to demonstrate that these discrete spectra are both accurate and robust in practice
We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution D with infinite (perhaps even uncountable) support...
详细信息
ISBN:
(纸本)9780898717013
We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution D with infinite (perhaps even uncountable) support Our goal is to test whether D has a given property of it is e-far nom it (in the statistical distance, with the L-1-distance measure) It is not difficult to see that for many natural distributions on infinite of uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there ale any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0,1] is uniform We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (stOC'2005) to the case of continuous [0, 1](n) cubes. We show that if a distribution D on [0,1](n) is monotone, then one can test if D is uniform with the sample complexity O(n/epsilon(2)) This result is optimal up to a polylogarithmic factor
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-e...
详细信息
ISBN:
(纸本)9781611975994
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-elements with range [-1, 1], computes an epsilon-additive approximate minimizer in (O) over tilde (n/epsilon(2)) oracle evaluations with high probability. This improves over the (O) over tilde (n(5/3)/epsilon(2)) oracle evaluation algorithm of Chakrabarty et al. (stOC 2017) and the (O) over tilde (n3(/2)/epsilon(2)) oracle evaluation algorithm of Hamoudi et al. Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function f with domain [0, 1](n) that satisfies partial derivative(2)f/partial derivative x(t)partial derivative x(j) of < 0 for all i not equal j and is L-Lipschitz with respect to the L-infinity-norm we give an algorithm that computes an epsilon-additive approximate minimizer with <(O)over tilde>(n . poly(L/epsilon)) function evaluation with high probability.
At the core of the Robertson-Seymour theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor [15]. A...
详细信息
ISBN:
(纸本)9781611975994
At the core of the Robertson-Seymour theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor [15]. An important step towards this structure theorem is the Flat Wall Theorem [14], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals). In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.
The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportio...
详细信息
ISBN:
(纸本)9781611975994
The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envy-freeness. It is well known that a proportional allocation among n agents can be found efficiently via simple protocols [16]. For envy-freeness, in a recent breakthrough, Aziz and Mackenzie [5] proposed a discrete and bounded envy-free protocol for any number of players. However, the protocol suffers from high multiple-exponential query complexity and it remains open to find simpler and more efficient envy-free protocols. In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their shares relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envy-freeness: its existence is guaranteed by that of an envy-free allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is listed in both [1] and [8] as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graph. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers of n query complexity of the envy-free protocol given in [5].
Using inclusion-exclusion, we can write the indicator function of a union of finitely many balls as an alternating sum of indicator functions of common intersections of balls. We exhibit abstract simplicial complexes ...
详细信息
Using inclusion-exclusion, we can write the indicator function of a union of finitely many balls as an alternating sum of indicator functions of common intersections of balls. We exhibit abstract simplicial complexes that correspond to minimal inclusion-exclusion formulas. They include the dual complex, as defined in [3], and are characterized by the independence of their simplices and by geometric realizations with the same underlying space as the dual complex.
暂无评论