2 Search Results for "Tsai, Wei-Tek"

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/DagRep.3.9.34
Cloud-based Software Crowdsourcing (Dagstuhl Seminar 13362)

Authors: Michael N. Huhns, Wei Li, and Wei-Tek Tsai

Published in: Dagstuhl Reports, Volume 3, Issue 9 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13362 "Cloud-based Software Crowdsourcing". In addition to providing enormous resources and utility-based computing, clouds also enable a new software development methodology by crowdsourcing, where participants either collaborate or compete with each other to develop software. Seminar topics included crowd platforms, modeling, social issues, development processes, and verification.
Cite as

Michael N. Huhns, Wei Li, and Wei-Tek Tsai. Cloud-based Software Crowdsourcing (Dagstuhl Seminar 13362). In Dagstuhl Reports, Volume 3, Issue 9, pp. 34-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{huhns_et_al:DagRep.3.9.34,
  author =	{Huhns, Michael N. and Li, Wei and Tsai, Wei-Tek},
  title =	{{Cloud-based Software Crowdsourcing (Dagstuhl Seminar 13362)}},
  pages =	{34--58},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{9},
  editor =	{Huhns, Michael N. and Li, Wei and Tsai, Wei-Tek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.9.34},
  URN =		{urn:nbn:de:0030-drops-43555},
  doi =		{10.4230/DagRep.3.9.34},
  annote =	{Keywords: Crowdsourcing, Software Development, Cloud Computing}
}
  • Refine by Author
  • 1 Huhns, Michael N.
  • 1 Li, Wei
  • 1 Tsai, Wei-Tek
  • 1 Tu, Ta-Wei

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Theory of computation → Discrete optimization

  • Refine by Keyword
  • 1 Cloud Computing
  • 1 Combinatorial Optimization
  • 1 Crowdsourcing
  • 1 Matroids
  • 1 Software Development
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2013
  • 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