SGSteven Ge
Steven Ge
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Steven Ge has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Toshiya Itoh
Tokyo Institute of Technology
5 shared publications Toshiya Itoh
1 shared publication
Latest Publications
- 21 February 2025
- Published by Springer Nature
- p. 196-214
Popularity on the 3D-Euclidean Stable Roommates
- 21 February 2025
- Published by Springer Nature
- p. 196-214
Popularity on the 3D-Euclidean Stable Roommates
- 15 October 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1023
Popularity on the roommate diversity problem
- 15 October 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1023
Popularity on the roommate diversity problem
- 9 December 2023
- Published by Springer Nature
- p. 316-329
Popularity on the Roommate Diversity Problem
- Open Access
Popularity on the 3D-Euclidean Stable Roommates
We study the 3D-Euclidean Multidimensional Stable Roommates problem, which asks whether a given set $V$ of $s\cdot n$ agents with a location in 3-dimensional Euclidean space can be partitioned into $n$ disjoint subsets $π= \{R_1 ,\dots , R_n\}$ with $|R_i| = s$ for each $R_i \in π$ such that $π$ is (strictly) popular, where $s$ is the room size. A partitioning is popular if there does not exist another partitioning in which more agents are better off than worse off. Computing a popular partition in a stable roommates game is NP-hard, even if the preferences are strict. The preference of an agent solely depends on the distance to its roommates. An agent prefers to be in a room where the sum of the distances to its roommates is small. We show that determining the existence of a strictly popular outcome in a 3D-Euclidean Multidimensional Stable Roommates game with room size $3$ is co-NP-hard.Open AccessPopularity on the 3D-Euclidean Stable Roommates
We study the 3D-Euclidean Multidimensional Stable Roommates problem, which asks whether a given set $V$ of $s\cdot n$ agents with a location in 3-dimensional Euclidean space can be partitioned into $n$ disjoint subsets $π= \{R_1 ,\dots , R_n\}$ with $|R_i| = s$ for each $R_i \in π$ such that $π$ is (strictly) popular, where $s$ is the room size. A partitioning is popular if there does not exist another partitioning in which more agents are better off than worse off. Computing a popular partition in a stable roommates game is NP-hard, even if the preferences are strict. The preference of an agent solely depends on the distance to its roommates. An agent prefers to be in a room where the sum of the distances to its roommates is small. We show that determining the existence of a strictly popular outcome in a 3D-Euclidean Multidimensional Stable Roommates game with room size $3$ is co-NP-hard. - 1 January 2022
- Published by Springer Nature
- p. 55-66
Characterization of the Imbalance Problem on Complete Bipartite Graphs
- 1 January 2022
- Published by Springer Nature
- p. 55-66
Characterization of the Imbalance Problem on Complete Bipartite Graphs
- Open Access
Characterization of the Imbalance Problem on Complete Bipartite Graphs
We study the imbalance problem on complete bipartite graphs. The imbalance problem is a graph layout problem and is known to be NP-complete. Graph layout problems find their applications in the optimization of networks for parallel computer architectures, VLSI circuit design, information retrieval, numerical analysis, computational biology, graph theory, scheduling and archaeology. In this paper, we give characterizations for the optimal solutions of the imbalance problem on complete bipartite graphs. Using the characterizations, we can solve the imbalance problem in $\mathcal{O}(\log(|V|) \cdot \log(\log(|V|)))$ time, when given the cardinalities of the parts of the graph, and verify whether a given solution is optimal in $O(|V|)$ time on complete bipartite graphs. We also introduce a restricted form of proper interval bipartite graphs on which the imbalance problem is solvable in $\mathcal{O}(c \cdot \log(|V|) \cdot \log(\log(|V|)))$ time, where $c = \mathcal{O}(|V|)$, by using the aforementioned characterizations.Open AccessCharacterization of the Imbalance Problem on Complete Bipartite Graphs
We study the imbalance problem on complete bipartite graphs. The imbalance problem is a graph layout problem and is known to be NP-complete. Graph layout problems find their applications in the optimization of networks for parallel computer architectures, VLSI circuit design, information retrieval, numerical analysis, computational biology, graph theory, scheduling and archaeology. In this paper, we give characterizations for the optimal solutions of the imbalance problem on complete bipartite graphs. Using the characterizations, we can solve the imbalance problem in $\mathcal{O}(\log(|V|) \cdot \log(\log(|V|)))$ time, when given the cardinalities of the parts of the graph, and verify whether a given solution is optimal in $O(|V|)$ time on complete bipartite graphs. We also introduce a restricted form of proper interval bipartite graphs on which the imbalance problem is solvable in $\mathcal{O}(c \cdot \log(|V|) \cdot \log(\log(|V|)))$ time, where $c = \mathcal{O}(|V|)$, by using the aforementioned characterizations.