the proceedings contain 192 papers. the topics discussed include: prior-independent auctions for heterogeneous bidders;impossibilities for obviously strategy-proof mechanisms;revenue maximization for buyers with costl...
the proceedings contain 192 papers. the topics discussed include: prior-independent auctions for heterogeneous bidders;impossibilities for obviously strategy-proof mechanisms;revenue maximization for buyers with costly participation;breaking the 3/4 barrier for approximate maximin share;combinatorial contracts beyond gross substitutes;on supermodular contracts and dense subgraphs;sorting pattern-avoiding permutations via 0–1 matrices forbidding product patterns;vertical decomposition in 3D and 4D with applications to line nearest-neighbor searching in 3D;dynamic dictionary with subconstant wasted bits per key;dynamic time warping;and dynamically maintaining the persistent homology of time series.
the proceedings contain 189 papers. the topics discussed include: dynamic algorithms for packing-covering LPs via multiplicative weight updates;maintaining expander decompositions via sparse cuts;fully dynamic exact e...
ISBN:
(纸本)9781611977554
the proceedings contain 189 papers. the topics discussed include: dynamic algorithms for packing-covering LPs via multiplicative weight updates;maintaining expander decompositions via sparse cuts;fully dynamic exact edge connectivity in sublinear time;faster deterministic worst-case fully dynamic all-pairs shortest paths via decremental hop-restricted shortest paths;dynamic matching with better-than-2 approximation in polylogarithmic update time;dynamic algorithms for maximum matching size;closing the gap between directed hopsets and shortcut sets;maximal k-edge-connected subgraphs in weighted graphs via local random contraction;faster and unified algorithms for diameter reducing shortcuts and minimum chain cover;near-linear time approximations for cut problems via fair cuts;fast discrepancy minimization with hereditary guarantees;a tight quasi-polynomial bound for global label min-cut;a tight quasi-polynomial bound for global label min-cut;a nearly-tight analysis of multipass pairing heaps;a tight analysis of slim heaps and smooth heaps;and short synchronizing words for random automata.
the single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single path. One of the most heavily studie...
ISBN:
(纸本)9781611977912
the single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single path. One of the most heavily studied SSUF objectives is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. this intriguing conjecture remains open. More so, there are arguably no non-trivial graph classes for which it is known to hold. We show that a slight weakening of it (with at most twice as large violations) holds for planar graphs. Our result is based on a connection to a highly structured discrepancy problem, whose repeated resolution allows us to successively reduce the number of paths used for each terminal, until we obtain an unsplittable flow. Moreover, our techniques also extend to simultaneous upper and lower bounds on the flow values. this also affirmatively answers a conjecture of Morell and Skutella for planar SSUF.
We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results ...
详细信息
ISBN:
(纸本)9781611977554
We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di)graph packing problems, namely the Triangle-Packing in Tournament problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the Induced 2-Path-Packing (I2PP) where we ask for a packing of k induced paths of length two in a graph. the existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, thomasse, Zehavi. acm Trans. algorithms, 2019], where they gave a kernel of O(k(3/2)) vertices and O(k(5/3)) vertices respectively. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT admits an (almost linear) kernel of k(1+ O(1)/root log k) vertices and that I2PP admits a kernel of O(k) vertices.
Given a d-dimensional continuous (resp. discrete) probability distribution mu and a discrete distribution nu, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to...
ISBN:
(纸本)9781611977912
Given a d-dimensional continuous (resp. discrete) probability distribution mu and a discrete distribution nu, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from mu to nu;we assume n to be the number of points in the support of the discrete distributions. In this paper, we present three approximation algorithms for the OT problem with strong provable guarantees. (i) Additive approximation for semi-discrete OT: For any parameter epsilon > 0, we present an algorithm that computes a semi-discrete transport plan (tau) over tilde with cost cent((tau) over tilde) <= cent(tau*) + epsilon in n(O(d)) log D/epsilon time;here, tau* is the optimal transport plan, D is the diameter of the supports of mu and nu, and we assume we have access to an oracle that outputs the mass of mu inside a constant-complexity region in O(1) time. Our algorithm works for several ground distances including the L-p-norm and the squared-Euclidean distance. (ii) Relative approximation for semi-discrete OT: For any parameter epsilon > 0, we present an algorithm that computes a semi-discrete transport plan (tau) over tilde with cost cent((tau) over tilde) <= (1 + epsilon)cent(tau*) in n log(n) . (epsilon(-1) log log n)(O(d)) expected time;here, tau* is the optimal transport plan, and we assume we have access to an oracle that outputs the mass of mu inside an orthogonal box in O(1) time, and the ground distance is any L-p norm. (iii) Relative approximation for discrete OT: For any parameter epsilon > 0, we present a Monte-Carlo algorithm that computes a transport plan (tau) over tilde with an expected cost cent((tau) over tilde) <= (1 + epsilon)cent(tau*) under any L-p norm in n log(n) . (epsilon(-1) log log n)(O(d)) time;here, tau* is an optimal transport plan and we assume that the spread of the supports of mu and nu is polynomially bounded.
We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or ed...
详细信息
ISBN:
(纸本)9781611977554
We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or edge-disjoint, and the graph can be undirected or directed. the family of cycles under consideration must satisfy two properties: it must be uncrossable and allow for an oracle access that finds a weight-minimal cycle in that family for given nonnegative edge weights or (in planar graphs) the union of all remaining cycles in that family after deleting a given subset of edges. Our setting generalizes many problems that were studied separately in the past. For example, three families that satisfy the above properties are (i) all cycles in a directed or undirected graph, (ii) all odd cycles in an undirected graph, and (iii) all cycles in an undirected graph that contain precisely one demand edge, where the demand edges form a subset of the edge set. the latter family (iii) corresponds to the classical disjoint paths problem in fully planar and bounded-genus instances. While constant-factor approximation algorithms were known for edge-disjoint paths in such instances, we improve the constant in the planar case and obtain the first such algorithms for vertex-disjoint paths. We also obtain approximate min-max theorems of the Erd}os{Posa type. For example, the minimum feedback vertex set in a planar digraph is at most 12 times the maximum number of vertex-disjoint cycles.
Two simple undirected graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality yields an equivalence relation on the family of graphs which is provably weaker t...
详细信息
ISBN:
(纸本)9781611977554
Two simple undirected graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality yields an equivalence relation on the family of graphs which is provably weaker than isomorphism. In this paper, we study cospectrality in relation to another well-studied relaxation of isomorphism, namely k-dimensional Weisfeiler-Leman ( k-WL) indistinguishability. Cospectrality with respect to standard graph matrices such as the adjacency or the Laplacian matrix yields a strictly finer equivalence relation than 2-WL indistinguishability. We show that individualising one vertex plus running 1-WL already subsumes cospectrality with respect to all such graph matrices. Building on this result, we resolve an open problem of Furer (2010) about spectral invariants and strengthen a result of Godsil (1981) about commute distances. Looking beyond 2-WL, we devise a hierarchy of graph matrices generalising the adjacency matrix such that k-WL indistinguishability after a fixed number of iterations can be captured as a spectral condition on these matrices. Precisely, we provide a spectral characterisation of k-WL indistinguishability after d iterations, for k;d is an element of N. Our results can be viewed as characterisations of homomorphism indistinguishability over certain graph classes in terms of matrix equations. the study of homomorphism indistinguishability is an emerging field, to which we contribute by extending the algebraic framework of Mancinska and Roberson (2020) and Grohe et al. (2022).
By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 P ' olya asked for which (0, 1)-matrices A it is possible to change some signs such that the permanent of...
详细信息
ISBN:
(纸本)9781611977554
By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 P ' olya asked for which (0, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding K-3,K-3 as a matching minor. this was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K-3,K-3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0, 1)-matrices can be computed efficiently. In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing-minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and K-3,K-3 which includes infinitely many non-Pfaffian graphs. the exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude K5,5 as a matching minor. this establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth.
the most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithmsthat improve the state-of-the-art for provable classical/quantum algorithms for SVP. ...
详细信息
the most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithmsthat improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results: (1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 \leq q \leq root n, our algorithm takes q13n+o(n) time and requires poly(n) \cdot q16n/q2 memory. this tradeoff, which ranges from enumeration (q = root n) to sieving (q constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In a quantum random access memory (QRAM) model, this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. this improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventhannualacm on symposium on theory of Computing (STOC), 2015, pp. 733--742] that has a time and space complexity 2n+o(n). (3) A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. this improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285--306] that has the same space complexity. the time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n), and our quantum algorithm in a QRA
Kuske and Schweikardt introduced the very expressive first-order counting logic FOC(P) to model database queries with counting operations. they showed that there is an efficient model-checking algorithm on graphs with...
详细信息
ISBN:
(纸本)9781611976465
Kuske and Schweikardt introduced the very expressive first-order counting logic FOC(P) to model database queries with counting operations. they showed that there is an efficient model-checking algorithm on graphs with bounded degree, while Grohe and Schweikardt showed that probably no such algorithm exists for trees of bounded depth. We analyze the fragment FO({>0}) of this logic. While we remove for example subtraction and comparison between two nonatomic counting terms, this logic remains quite expressive: We allow nested counting and comparison between counting terms and arbitrarily large numbers. Our main result is an approximation scheme of the model-checking problem for FO({> 0}) that runs in linear fpt time on structures with bounded expansion. this scheme either gives the correct answer or says "I do not know." the latter answer may only be given if small perturbations in the number-symbols of the formula could make it both satisfied and unsatisfied. this is complemented by showing that exactly solving the model-checking problem for FO({> 0}) is already hard on trees of bounded depth and just slightly increasing the expressiveness of FO({> 0}) makes even approximation hard on trees.
暂无评论