4 Search Results for "Hong, Liu"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.21
Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds

Authors: Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted R₁ and R₂. In round R₁, the capacity of each school is fixed and mechanism M₁ finds a student optimal stable matching. In round R₂, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results: the first simply disallows any re-allocations in round R₂, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round R₂ under certain settings.
Cite as

Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani. Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.FSTTCS.2020.21,
  author =	{Gajulapalli, Karthik and Liu, James A. and Mai, Tung and Vazirani, Vijay V.},
  title =	{{Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.21},
  URN =		{urn:nbn:de:0030-drops-132626},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.21},
  annote =	{Keywords: stable matching, mechanism design, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.53
Optimal Nonpreemptive Scheduling in a Smart Grid Model

Authors: Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their requests can be served. The grid controller, upon receiving power requests, schedules each request within the specified interval. The electricity cost is measured by a convex function of the load in each timeslot. The objective is to schedule all requests with the minimum total electricity cost. Previous work has studied cases where jobs have unit power requirement and unit duration. We extend the study to arbitrary power requirement and duration, which has been shown to be NP-hard. We give the first online algorithm for the general problem, and prove that the worst case competitive ratio is asymptotically optimal. We also prove that the problem is fixed parameter tractable. Due to space limit, the missing proofs are presented in the full paper.
Cite as

Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong. Optimal Nonpreemptive Scheduling in a Smart Grid Model. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ISAAC.2016.53,
  author =	{Liu, Fu-Hong and Liu, Hsiang-Hsuan and Wong, Prudence W. H.},
  title =	{{Optimal Nonpreemptive Scheduling in a Smart Grid Model}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.53},
  URN =		{urn:nbn:de:0030-drops-68252},
  doi =		{10.4230/LIPIcs.ISAAC.2016.53},
  annote =	{Keywords: Scheduling, Smart Grid, Convex function cost, Fixed parameter tractable, Online algorithms, Non-preemptive}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.54
Distributed and Robust Support Vector Machine

Authors: Yangwei Liu, Hu Ding, Ziyun Huang, and Jinhui Xu

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
In this paper, we consider the distributed version of Support Vector Machine (SVM) under the coordinator model, where all input data (i.e., points in R^d space) of SVM are arbitrarily distributed among k nodes in some network with a coordinator which can communicate with all nodes. We investigate two variants of this problem, with and without outliers. For distributed SVM without outliers, we prove a lower bound on the communication complexity and give a distributed (1-epsilon)-approximation algorithm to reach this lower bound, where epsilon is a user specified small constant. For distributed SVM with outliers, we present a (1-epsilon)-approximation algorithm to explicitly remove the influence of outliers. Our algorithm is based on a deterministic distributed top t selection algorithm with communication complexity of O(k log (t)) in the coordinator model. Experimental results on benchmark datasets confirm the theoretical guarantees of our algorithms.
Cite as

Yangwei Liu, Hu Ding, Ziyun Huang, and Jinhui Xu. Distributed and Robust Support Vector Machine. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ISAAC.2016.54,
  author =	{Liu, Yangwei and Ding, Hu and Huang, Ziyun and Xu, Jinhui},
  title =	{{Distributed and Robust Support Vector Machine}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.54},
  URN =		{urn:nbn:de:0030-drops-68221},
  doi =		{10.4230/LIPIcs.ISAAC.2016.54},
  annote =	{Keywords: Distributed Algorithm, Communication Complexity, Robust Algorithm, SVM}
}
Document
DOI: 10.4230/DagSemProc.09181.3
09181 Working Group on Hybridization between R&S, DoE and Optimization

Authors: Chun-Hung Chen, Liu Hong, Paul B. Kantor, David P. Morton, Juta Pichitlamken, and Matthias Seeger

Published in: Dagstuhl Seminar Proceedings, Volume 9181, Sampling-based Optimization in the Presence of Uncertainty (2009)

Abstract
This is the report of the working group on the relation between, or hybrid combination of design experiment optimization and R&S. The rapporteur, Paul Kantor, learned a great deal at the conference which he summarized by sharing the cartoon shown here. ("A student asking the teacher'... may i be excused, my is full" (from a 1986 cartoon by Gary Larson) - omitted here for copyright reasons).
Cite as

Chun-Hung Chen, Liu Hong, Paul B. Kantor, David P. Morton, Juta Pichitlamken, and Matthias Seeger. 09181 Working Group on Hybridization between R&S, DoE and Optimization. In Sampling-based Optimization in the Presence of Uncertainty. Dagstuhl Seminar Proceedings, Volume 9181, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.09181.3,
  author =	{Chen, Chun-Hung and Hong, Liu and Kantor, Paul B. and Morton, David P. and Pichitlamken, Juta and Seeger, Matthias},
  title =	{{09181 Working Group on Hybridization between R\&S, DoE and Optimization}},
  booktitle =	{Sampling-based Optimization in the Presence of Uncertainty},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9181},
  editor =	{J\"{u}rgen Branke and Barry L. Nelson and Warren Buckler Powell and Thomas J. Santner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09181.3},
  URN =		{urn:nbn:de:0030-drops-21172},
  doi =		{10.4230/DagSemProc.09181.3},
  annote =	{Keywords: }
}
  • Refine by Author
  • 1 Chen, Chun-Hung
  • 1 Ding, Hu
  • 1 Gajulapalli, Karthik
  • 1 Hong, Liu
  • 1 Huang, Ziyun
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics

  • Refine by Keyword
  • 1 Communication Complexity
  • 1 Convex function cost
  • 1 Distributed Algorithm
  • 1 Fixed parameter tractable
  • 1 NP-Hardness
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2016
  • 1 2009
  • 1 2020

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