Document

RANDOM

**Published in:** LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

In a complete graph K_n with edge weights drawn independently from a uniform distribution U(0,1) (or alternatively an exponential distribution Exp(1)), let T_1 be the MST (the spanning tree of minimum weight) and let T_k be the MST after deletion of the edges of all previous trees T_i, i<k. We show that each tree’s weight w(T_k) converges in probability to a constant gamma_k with 2k-2 sqrt k < gamma_k < 2k+2 sqrt k, and we conjecture that gamma_k = 2k-1+o(1). The problem is distinct from that of [Alan Frieze and Tony Johansson, 2018], finding k MSTs of combined minimum weight, and the combined cost for two trees in their problem is, asymptotically, strictly smaller than our gamma_1+gamma_2.
Our results also hold (and mostly are derived) in a multigraph model where edge weights for each vertex pair follow a Poisson process; here we additionally have E(w(T_k)) -> gamma_k. Thinking of an edge of weight w as arriving at time t=n w, Kruskal’s algorithm defines forests F_k(t), each initially empty and eventually equal to T_k, with each arriving edge added to the first F_k(t) where it does not create a cycle. Using tools of inhomogeneous random graphs we obtain structural results including that C_1(F_k(t))/n, the fraction of vertices in the largest component of F_k(t), converges in probability to a function rho_k(t), uniformly for all t, and that a giant component appears in F_k(t) at a time t=sigma_k. We conjecture that the functions rho_k tend to time translations of a single function, rho_k(2k+x) -> rho_infty(x) as k -> infty, uniformly in x in R.
Simulations and numerical computations give estimated values of gamma_k for small k, and support the conjectures stated above.

Svante Janson and Gregory B. Sorkin. Successive Minimum Spanning Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{janson_et_al:LIPIcs.APPROX-RANDOM.2019.60, author = {Janson, Svante and Sorkin, Gregory B.}, title = {{Successive Minimum Spanning Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {60:1--60:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.60}, URN = {urn:nbn:de:0030-drops-112759}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.60}, annote = {Keywords: miminum spanning tree, second-cheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multi-type branching process, functional fixed point, robust optimization, Kruskal’s algorithm} }

Document

**Published in:** Dagstuhl Reports, Volume 3, Issue 8 (2013)

This report documents the program and the outcomes of Dagstuhl Seminar
13331 "Exponential Algorithms: Algorithms and Complexity Beyond
Polynomial Time". Problems are often solved in practice by algorithms with worst-case exponential time complexity. It is of interest to find the fastest algorithms for a given problem, be it polynomial, exponential, or something in between. The focus of the Seminar is on finer-grained notions of complexity
than np-completeness and on understanding the exact complexities of problems.
The report provides a rationale for the workshop and chronicles the presentations at the workshop. The report notes the progress on the open problems posed at the past workshops on the same topic. It also reports a collection of results that cite the presentations at the previous seminar. The docoument presents the collection of the abstracts of the results presented
at the Seminar. It also presents a compendium of open problems.

Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, and Ryan Williams. Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). In Dagstuhl Reports, Volume 3, Issue 8, pp. 40-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{husfeldt_et_al:DagRep.3.8.40, author = {Husfeldt, Thore and Paturi, Ramamohan and Sorkin, Gregory B. and Williams, Ryan}, title = {{Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331)}}, pages = {40--72}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {3}, number = {8}, editor = {Husfeldt, Thore and Paturi, Ramamohan and Sorkin, Gregory B. and Williams, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.8.40}, URN = {urn:nbn:de:0030-drops-43422}, doi = {10.4230/DagRep.3.8.40}, annote = {Keywords: Algorithms, exponential time algorithms, exact algorithms, computational complexity, satisfiability} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)

A decade before NP-completeness became the
lens through which Computer Science views computationally hard
problems, beautiful algorithms were discovered that are much better
than exhaustive search, for example
Bellman's 1962 dynamic programming treatment of the Traveling Salesman problem
and Ryser's 1963 inclusion--exclusion formula for the permanent.

Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin. 10441 Abstracts Collection – Exact Complexity of NP-hard Problems. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{husfeldt_et_al:DagSemProc.10441.1, author = {Husfeldt, Thore and Kratsch, Dieter and Paturi, Ramamohan and Sorkin, Gregory B.}, title = {{10441 Abstracts Collection – Exact Complexity of NP-hard Problems}}, booktitle = {Exact Complexity of NP-hard Problems}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10441}, editor = {Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.1}, URN = {urn:nbn:de:0030-drops-29363}, doi = {10.4230/DagSemProc.10441.1}, annote = {Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail