5 Search Results for "Lu, Wei"

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.63
Subquadratic Weighted Matroid Intersection Under Rank Oracles

Authors: Ta-Wei Tu

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Given two matroids ℳ₁ = (V, ℐ₁) and ℳ₂ = (V, ℐ₂) over an n-element integer-weighted ground set V, the weighted matroid intersection problem aims to find a common independent set S^* ∈ ℐ₁ ∩ ℐ₂ maximizing the weight of S^*. In this paper, we present a simple deterministic algorithm for weighted matroid intersection using Õ(nr^{3/4} log{W}) rank queries, where r is the size of the largest intersection of ℳ₁ and ℳ₂ and W is the maximum weight. This improves upon the best previously known Õ(nr log{W}) algorithm given by Lee, Sidford, and Wong [FOCS'15], and is the first subquadratic algorithm for polynomially-bounded weights under the standard independence or rank oracle models. The main contribution of this paper is an efficient algorithm that computes shortest-path trees in weighted exchange graphs.
Cite as

Ta-Wei Tu. Subquadratic Weighted Matroid Intersection Under Rank Oracles. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{tu:LIPIcs.ISAAC.2022.63,
  author =	{Tu, Ta-Wei},
  title =	{{Subquadratic Weighted Matroid Intersection Under Rank Oracles}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{63:1--63:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.63},
  URN =		{urn:nbn:de:0030-drops-173485},
  doi =		{10.4230/LIPIcs.ISAAC.2022.63},
  annote =	{Keywords: Matroids, Weighted Matroid Intersection, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2021.6
Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting

Authors: Shangqi Lu and Yufei Tao

Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)

Abstract
In ICDT'19, Kara, Ngo, Nikolic, Olteanu, and Zhang gave a structure which maintains the number T of triangles in an undirected graph G = (V, E) along with the edge insertions/deletions in G. Using O(m) space (m = |E|), their structure supports an update in O(√m log m) amortized time which is optimal (up to polylog factors) subject to the OMv-conjecture (Henzinger, Krinninger, Nanongkai, and Saranurak, STOC'15). Aiming to improve the update efficiency, we study: - the optimal tradeoff between update time and approximation quality. We require a structure to provide the (ε, Γ)-guarantee: when queried, it should return an estimate t of T that has relative error at most ε if T ≥ Γ, or an absolute error at most ε ⋅ Γ, otherwise. We prove that, under any ε ≤ 0.49 and subject to the OMv-conjecture, no structure can guarantee O(m^{0.5-δ}/Γ) expected amortized update time and O(m^{2/3-δ}) query time simultaneously for any constant δ > 0; this is true for Γ = m^c of any constant c in [0, 1/2). We match the lower bound with a structure that ensures Õ((1/ε)³ ⋅ √m/Γ) amortized update time with high probability, and O(1) query time. - (for exact counting) how to achieve arboricity-sensitive update time. For any 1 ≤ Γ ≤ √m, we describe a structure of O(min{α m + m log m, (m/Γ)²}) space that maintains T precisely, and supports an update in Õ(min{α + Γ, √m}) amortized time, where α is the largest arboricity of G in history (and does not need to be known). Our structure reconstructs the aforementioned ICDT'19 result up to polylog factors by setting Γ = √m, but achieves Õ(m^{0.5-δ}) update time as long as α = O(m^{0.5-δ}).
Cite as

Shangqi Lu and Yufei Tao. Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.ICDT.2021.6,
  author =	{Lu, Shangqi and Tao, Yufei},
  title =	{{Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting}},
  booktitle =	{24th International Conference on Database Theory (ICDT 2021)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-179-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{186},
  editor =	{Yi, Ke and Wei, Zhewei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.6},
  URN =		{urn:nbn:de:0030-drops-137146},
  doi =		{10.4230/LIPIcs.ICDT.2021.6},
  annote =	{Keywords: Triangle Counting, Data Structures, Lower Bounds, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.24
On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback

Authors: Wei Chen and Binghui Peng

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
In this paper, we study the adaptivity gap of the influence maximization problem under the independent cascade model when full-adoption feedback is available. Our main results are to derive upper bounds on several families of well-studied influence graphs, including in-arborescences, out-arborescences and bipartite graphs. Especially, we prove that the adaptivity gap for the in-arborescences is between [e/(e-1), 2e/(e-1)], and for the out-arborescences the gap is between [e/(e-1), 2]. These are the first constant upper bounds in the full-adoption feedback model. Our analysis provides several novel ideas to tackle the correlated feedback appearing in adaptive stochastic optimization, which may be of independent interest.
Cite as

Wei Chen and Binghui Peng. On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2019.24,
  author =	{Chen, Wei and Peng, Binghui},
  title =	{{On Adaptivity Gaps of Influence Maximization Under the Independent Cascade Model with Full-Adoption Feedback}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.24},
  URN =		{urn:nbn:de:0030-drops-115208},
  doi =		{10.4230/LIPIcs.ISAAC.2019.24},
  annote =	{Keywords: Adaptive influence maximization, adaptivity gap, full-adoption feedback}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.12
Specification and Implementation of Replicated List: The Jupiter Protocol Revisited

Authors: Hengfeng Wei, Yu Huang, and Jian Lu

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
The replicated list object is frequently used to model the core functionality of replicated collaborative text editing systems. Since 1989, the convergence property has been a common specification of a replicated list object. Recently, Attiya et al. proposed the strong/weak list specification and conjectured that the well-known Jupiter protocol satisfies the weak list specification. The major obstacle to proving this conjecture is the mismatch between the global property on all replica states prescribed by the specification and the local view each replica maintains in Jupiter using data structures like 1D buffer or 2D state space. To address this issue, we propose CJupiter (Compact Jupiter) based on a novel data structure called n-ary ordered state space for a replicated client/server system with n clients. At a high level, CJupiter maintains only a single n-ary ordered state space which encompasses exactly all states of each replica. We prove that CJupiter and Jupiter are equivalent and that CJupiter satisfies the weak list specification, thus solving the conjecture above.
Cite as

Hengfeng Wei, Yu Huang, and Jian Lu. Specification and Implementation of Replicated List: The Jupiter Protocol Revisited. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{wei_et_al:LIPIcs.OPODIS.2018.12,
  author =	{Wei, Hengfeng and Huang, Yu and Lu, Jian},
  title =	{{Specification and Implementation of Replicated List: The Jupiter Protocol Revisited}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.12},
  URN =		{urn:nbn:de:0030-drops-100720},
  doi =		{10.4230/LIPIcs.OPODIS.2018.12},
  annote =	{Keywords: Collaborative text editing systems, Replicated list, Concurrency control, Strong/weak list specification, Operational transformation, Jupiter protocol}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.41
Center Point of Simple Area Feature Based on Triangulation Skeleton Graph (Short Paper)

Authors: Wei Lu and Tinghua Ai

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
In the area of cartography and geographic information science, the center points of area features are related to many fields. The centroid is a conventional choice of center point of area feature. However, it is not suitable for features with a complex shape for the center point may be outside the area or not fit the visual center so well. This paper proposes a novel method to calculate the center point of area feature based on triangulation skeleton graph. This paper defines two kinds of centrality of vertices in skeleton graph according to the centrality theory in graph and network analysis. Through the measurement of vertices centrality, the center points of polygon area features are defined as the vertices with maximum centrality.
Cite as

Wei Lu and Tinghua Ai. Center Point of Simple Area Feature Based on Triangulation Skeleton Graph (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 41:1-41:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.GISCIENCE.2018.41,
  author =	{Lu, Wei and Ai, Tinghua},
  title =	{{Center Point of Simple Area Feature Based on Triangulation Skeleton Graph}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{41:1--41:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.41},
  URN =		{urn:nbn:de:0030-drops-93699},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.41},
  annote =	{Keywords: Shape Center, Triangulation Skeleton Graph, Graph Centrality}
}
  • Refine by Author
  • 1 Ai, Tinghua
  • 1 Chen, Wei
  • 1 Huang, Yu
  • 1 Lu, Jian
  • 1 Lu, Shangqi
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Distributed computing methodologies
  • 1 Human-centered computing → Collaborative and social computing systems and tools
  • 1 Information systems → Geographic information systems
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Matroids and greedoids
  • Show More...

  • Refine by Keyword
  • 1 Adaptive influence maximization
  • 1 Collaborative text editing systems
  • 1 Combinatorial Optimization
  • 1 Concurrency control
  • 1 Data Structures
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 1 2018
  • 1 2021
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact