File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-031-39344-0_3
- Scopus: eid_2-s2.0-85171456835
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Generalized Sorting with Predictions Revisited
| Title | Generalized Sorting with Predictions Revisited |
|---|---|
| Authors | |
| Keywords | Forbidden Comparison Generalized Sorting Predictions |
| Issue Date | 26-Aug-2023 |
| Publisher | Springer |
| Abstract | This paper presents a novel algorithm for the generalized sorting problem with predictions, which involves determining a total ordering of an underlying directed graph using as few probes as possible. Specifically, we consider the problem of sorting an undirected graph with predicted edge directions. Our proposed algorithm is a Monte Carlo approach that has a polynomial-time complexity, which uses �(�log�+�) probes with probability at least 1−�−Θ(�), where n is the number of vertices in the graph and w is the number of mispredicted edges. Our approach involves partitioning the vertices of the graph into O(w) disjoint verified directed paths, which can reduce the number of probes required. Lu et al. [11] introduced a bound of �(�log�+�) for the number of probes, which was the only known result in this setting. Our bound reduces the factor �(log�) to �(log�). |
| Persistent Identifier | http://hdl.handle.net/10722/338129 |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Chan, TH | - |
| dc.contributor.author | Sun, E | - |
| dc.contributor.author | Wang, B | - |
| dc.date.accessioned | 2024-03-11T10:26:28Z | - |
| dc.date.available | 2024-03-11T10:26:28Z | - |
| dc.date.issued | 2023-08-26 | - |
| dc.identifier.uri | http://hdl.handle.net/10722/338129 | - |
| dc.description.abstract | <p>This paper presents a novel algorithm for the generalized sorting problem with predictions, which involves determining a total ordering of an underlying directed graph using as few probes as possible. Specifically, we consider the problem of sorting an undirected graph with predicted edge directions. Our proposed algorithm is a Monte Carlo approach that has a polynomial-time complexity, which uses �(�log�+�) probes with probability at least 1−�−Θ(�), where <em>n</em> is the number of vertices in the graph and <em>w</em> is the number of mispredicted edges. Our approach involves partitioning the vertices of the graph into <em>O</em>(<em>w</em>) disjoint verified directed paths, which can reduce the number of probes required. Lu et al. [<a title="Lu, P., Ren, X., Sun, E., Zhang, Y.: Generalized sorting with predictions. In: SOSA, pp. 111–117. SIAM (2021)" href="https://link.springer.com/chapter/10.1007/978-3-031-39344-0_3#ref-CR11">11</a>] introduced a bound of �(�log�+�) for the number of probes, which was the only known result in this setting. Our bound reduces the factor �(log�) to �(log�).<br></p> | - |
| dc.language | eng | - |
| dc.publisher | Springer | - |
| dc.relation.ispartof | Frontier of Algorithmic Wisdom - International Joint Conference, IJTCS-FAW 2023 (14/08/2023-18/08/2023, Macau) | - |
| dc.subject | Forbidden Comparison | - |
| dc.subject | Generalized Sorting | - |
| dc.subject | Predictions | - |
| dc.title | Generalized Sorting with Predictions Revisited | - |
| dc.type | Conference_Paper | - |
| dc.identifier.doi | 10.1007/978-3-031-39344-0_3 | - |
| dc.identifier.scopus | eid_2-s2.0-85171456835 | - |
| dc.identifier.volume | 13933 | - |
| dc.identifier.spage | 29 | - |
| dc.identifier.epage | 41 | - |