Search Results

Documents authored by Ng, Kang Feng

Found 16 Possible Name Variants:

Ng, Kang Feng

Document
DOI: 10.4230/LIPIcs.FSCD.2018.17
A Diagrammatic Axiomatisation of Fermionic Quantum Circuits

Authors: Amar Hadzihasanovic, Giovanni de Felice, and Kang Feng Ng

Published in: LIPIcs, Volume 108, 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)

Abstract
We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in the language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are quantum systems of finitely many local fermionic modes, with operations that preserve or reverse the parity (number of particles mod 2) of states, and the tensor product, corresponding to the composition of two systems, as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. We conclude by showing, as an example, how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language.
Cite as

Amar Hadzihasanovic, Giovanni de Felice, and Kang Feng Ng. A Diagrammatic Axiomatisation of Fermionic Quantum Circuits. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 108, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hadzihasanovic_et_al:LIPIcs.FSCD.2018.17,
  author =	{Hadzihasanovic, Amar and de Felice, Giovanni and Ng, Kang Feng},
  title =	{{A Diagrammatic Axiomatisation of Fermionic Quantum Circuits}},
  booktitle =	{3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-077-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{108},
  editor =	{Kirchner, H\'{e}l\`{e}ne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2018.17},
  URN =		{urn:nbn:de:0030-drops-91873},
  doi =		{10.4230/LIPIcs.FSCD.2018.17},
  annote =	{Keywords: Fermionic Quantum Computing, String Diagrams, Categorical Quantum Mechanics}
}

Feng, Lu

Document
DOI: 10.4230/OASIcs.MCPS.2014.94
A Safety Argument Strategy for PCA Closed-Loop Systems: A Preliminary Proposal

Authors: Lu Feng, Andrew L. King, Sanjian Chen, Anaheed Ayoub, Junkil Park, Nicola Bezzo, Oleg Sokolsky, and Insup Lee

Published in: OASIcs, Volume 36, 5th Workshop on Medical Cyber-Physical Systems (2014)

Abstract
The emerging network-enabled medical devices impose new challenges for the safety assurance of medical cyber-physical systems (MCPS). In this paper, we present a case study of building a high-level safety argument for a patient-controlled analgesia (PCA) closed-loop system, with the purpose of exploring potential methodologies for assuring the safety of MCPS.
Cite as

Lu Feng, Andrew L. King, Sanjian Chen, Anaheed Ayoub, Junkil Park, Nicola Bezzo, Oleg Sokolsky, and Insup Lee. A Safety Argument Strategy for PCA Closed-Loop Systems: A Preliminary Proposal. In 5th Workshop on Medical Cyber-Physical Systems. Open Access Series in Informatics (OASIcs), Volume 36, pp. 94-99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:OASIcs.MCPS.2014.94,
  author =	{Feng, Lu and King, Andrew L. and Chen, Sanjian and Ayoub, Anaheed and Park, Junkil and Bezzo, Nicola and Sokolsky, Oleg and Lee, Insup},
  title =	{{A Safety Argument Strategy for PCA Closed-Loop Systems: A Preliminary Proposal}},
  booktitle =	{5th Workshop on Medical Cyber-Physical Systems},
  pages =	{94--99},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-66-8},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{36},
  editor =	{Turau, Volker and Kwiatkowska, Marta and Mangharam, Rahul and Weyer, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.MCPS.2014.94},
  URN =		{urn:nbn:de:0030-drops-45263},
  doi =		{10.4230/OASIcs.MCPS.2014.94},
  annote =	{Keywords: Medical Cyber-Physical Systems, Safety Argument, Assurance Cases, Patient-Controlled Analgesia Infusion Pump, Closed-Loop Systems}
}

Feng, Qi

Document
DOI: 10.4230/OASIcs.FAB.2021.5
Dynamic Curves for Decentralized Autonomous Cryptocurrency Exchanges

Authors: Bhaskar Krishnamachari, Qi Feng, and Eugenio Grippo

Published in: OASIcs, Volume 92, 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)

Abstract
One of the exciting recent developments in decentralized finance (DeFi) has been the development of decentralized cryptocurrency exchanges that can autonomously handle conversion between different cryptocurrencies. Decentralized exchange protocols such as Uniswap, Curve and other types of Automated Market Makers (AMMs) maintain a liquidity pool (LP) of two or more assets constrained to maintain at all times a mathematical relation to each other, defined by a given function or curve. Examples of such functions are the constant-sum and constant-product AMMs. Existing systems however suffer from several challenges. They require external arbitrageurs to restore the price of tokens in the pool to match the market price. Such activities can potentially drain resources from the liquidity pool. In particular dramatic market price changes can result in low liquidity with respect to one or more of the assets and reduce the total value of the LP. We propose in this work a new approach to constructing the AMM by proposing the idea of dynamic curves. It utilizes input from a market price oracle to modify the mathematical relationship between the assets so that the pool price continuously and automatically adjusts to be identical to the market price. This approach eliminates arbitrage opportunities and, as we show through simulations, maintains liquidity in the LP for all assets and the total value of the LP over a wide range of market prices.
Cite as

Bhaskar Krishnamachari, Qi Feng, and Eugenio Grippo. Dynamic Curves for Decentralized Autonomous Cryptocurrency Exchanges. In 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021). Open Access Series in Informatics (OASIcs), Volume 92, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{krishnamachari_et_al:OASIcs.FAB.2021.5,
  author =	{Krishnamachari, Bhaskar and Feng, Qi and Grippo, Eugenio},
  title =	{{Dynamic Curves for Decentralized Autonomous Cryptocurrency Exchanges}},
  booktitle =	{4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)},
  pages =	{5:1--5:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-196-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{92},
  editor =	{Gramoli, Vincent and Sadoghi, Mohammad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2021.5},
  URN =		{urn:nbn:de:0030-drops-139911},
  doi =		{10.4230/OASIcs.FAB.2021.5},
  annote =	{Keywords: Decentralized Exchange, Automated Market Maker, Decentralized Finance, Dynamic Curves}
}

Kang, Hong Jin

Document
Artifact
DOI: 10.4230/DARTS.5.2.10
Semantic Patches for Java Program Transformation (Artifact)

Authors: Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo

Published in: DARTS, Volume 5, Issue 2, Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
The program transformation tool Coccinelle is designed for making changes that is required in many locations within a software project. It has been shown to be useful for C code and has been been adopted for use in the Linux kernel by many developers. Over 6000 commits mentioning the use of Coccinelle have been made in the Linux kernel. Our artifact, Coccinelle4J, is an extension to Coccinelle in order for it to apply program transformations to Java source code. This artifact accompanies our experience report "Semantic Patches for Java Program Transformation", in which we show a case study of applying code transformations to upgrade usage of deprecated Android API methods to replacement API methods.
Cite as

Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo. Semantic Patches for Java Program Transformation (Artifact). In Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 2, pp. 10:1-10:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{kang_et_al:DARTS.5.2.10,
  author =	{Kang, Hong Jin and Thung, Ferdian and Lawall, Julia and Muller, Gilles and Jiang, Lingxiao and Lo, David},
  title =	{{Semantic Patches for Java Program Transformation}},
  pages =	{10:1--10:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{2},
  editor =	{Kang, Hong Jin and Thung, Ferdian and Lawall, Julia and Muller, Gilles and Jiang, Lingxiao and Lo, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.5.2.10},
  URN =		{urn:nbn:de:0030-drops-107875},
  doi =		{10.4230/DARTS.5.2.10},
  annote =	{Keywords: Java, semantic patches, automatic program transformation}
}
Document
Experience Report
DOI: 10.4230/LIPIcs.ECOOP.2019.22
Semantic Patches for Java Program Transformation (Experience Report)

Authors: Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
Developing software often requires code changes that are widespread and applied to multiple locations. There are tools for Java that allow developers to specify patterns for program matching and source-to-source transformation. However, to our knowledge, none allows for transforming code based on its control-flow context. We prototype Coccinelle4J, an extension to Coccinelle, which is a program transformation tool designed for widespread changes in C code, in order to work on Java source code. We adapt Coccinelle to be able to apply scripts written in the Semantic Patch Language (SmPL), a language provided by Coccinelle, to Java source files. As a case study, we demonstrate the utility of Coccinelle4J with the task of API migration. We show 6 semantic patches to migrate from deprecated Android API methods on several open source Android projects. We describe how SmPL can be used to express several API migrations and justify several of our design decisions.
Cite as

Hong Jin Kang, Ferdian Thung, Julia Lawall, Gilles Muller, Lingxiao Jiang, and David Lo. Semantic Patches for Java Program Transformation (Experience Report). In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 22:1-22:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kang_et_al:LIPIcs.ECOOP.2019.22,
  author =	{Kang, Hong Jin and Thung, Ferdian and Lawall, Julia and Muller, Gilles and Jiang, Lingxiao and Lo, David},
  title =	{{Semantic Patches for Java Program Transformation}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{22:1--22:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.22},
  URN =		{urn:nbn:de:0030-drops-108140},
  doi =		{10.4230/LIPIcs.ECOOP.2019.22},
  annote =	{Keywords: Program transformation, Java}
}

Feng, Yulin

Document
DOI: 10.4230/DagSemRep.174
Object-Oriented Software Development (Dagstuhl Seminar 9715)

Authors: Hans-Dieter Erich, Yulin Feng, David Kung, and Grit Denker

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Hans-Dieter Erich, Yulin Feng, David Kung, and Grit Denker. Object-Oriented Software Development (Dagstuhl Seminar 9715). Dagstuhl Seminar Report 174, pp. 1-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{erich_et_al:DagSemRep.174,
  author =	{Erich, Hans-Dieter and Feng, Yulin and Kung, David and Denker, Grit},
  title =	{{Object-Oriented Software Development (Dagstuhl Seminar 9715)}},
  pages =	{1--35},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{174},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.174},
  URN =		{urn:nbn:de:0030-drops-150616},
  doi =		{10.4230/DagSemRep.174},
}

Kang, Mihyun

Document
DOI: 10.4230/LIPIcs.AofA.2020.13
Counting Cubic Maps with Large Genus

Authors: Zhicheng Gao and Mihyun Kang

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We derive an asymptotic expression for the number of cubic maps on orientable surfaces when the genus is proportional to the number of vertices. Let Σ_g denote the orientable surface of genus g and θ=g/n∈ (0,1/2). Given g,n∈ ℕ with g→ ∞ and n/2-g→ ∞ as n→ ∞, the number C_{n,g} of cubic maps on Σ_g with 2n vertices satisfies C_{n,g} ∼ (g!)² α(θ) β(θ)ⁿ γ(θ)^{2g}, as g→ ∞, where α(θ),β(θ),γ(θ) are differentiable functions in (0,1/2). This also leads to the asymptotic number of triangulations (as the dual of cubic maps) with large genus. When g/n lies in a closed subinterval of (0,1/2), the asymptotic formula can be obtained using a local limit theorem. The saddle-point method is applied when g/n→ 0 or g/n→ 1/2.
Cite as

Zhicheng Gao and Mihyun Kang. Counting Cubic Maps with Large Genus. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.AofA.2020.13,
  author =	{Gao, Zhicheng and Kang, Mihyun},
  title =	{{Counting Cubic Maps with Large Genus}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.13},
  URN =		{urn:nbn:de:0030-drops-120437},
  doi =		{10.4230/LIPIcs.AofA.2020.13},
  annote =	{Keywords: cubic maps, triangulations, cubic graphs on surfaces, generating functions, asymptotic enumeration, local limit theorem, saddle-point method}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.18
The Giant Component and 2-Core in Sparse Random Outerplanar Graphs

Authors: Mihyun Kang and Michael Missethan

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
Let A(n,m) be a graph chosen uniformly at random from the class of all vertex-labelled outerplanar graphs with n vertices and m edges. We consider A(n,m) in the sparse regime when m=n/2+s for s=o(n). We show that with high probability the giant component in A(n,m) emerges at m=n/2+O (n^{2/3}) and determine the typical order of the 2-core. In addition, we prove that if s=ω(n^{2/3}), with high probability every edge in A(n,m) belongs to at most one cycle.
Cite as

Mihyun Kang and Michael Missethan. The Giant Component and 2-Core in Sparse Random Outerplanar Graphs. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kang_et_al:LIPIcs.AofA.2020.18,
  author =	{Kang, Mihyun and Missethan, Michael},
  title =	{{The Giant Component and 2-Core in Sparse Random Outerplanar Graphs}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.18},
  URN =		{urn:nbn:de:0030-drops-120488},
  doi =		{10.4230/LIPIcs.AofA.2020.18},
  annote =	{Keywords: giant component, core, outerplanar graphs, singularity analysis}
}
Document
Keynote Speakers
DOI: 10.4230/LIPIcs.AofA.2018.7
Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers)

Authors: Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We consider k-dimensional random simplicial complexes that are generated from the binomial random (k+1)-uniform hypergraph by taking the downward-closure, where k >= 2. For each 1 <= j <= k-1, we determine when all cohomology groups with coefficients in F_2 from dimension one up to j vanish and the zero-th cohomology group is isomorphic to F_2. This property is not monotone, but nevertheless we show that it has a single sharp threshold. Moreover, we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. Furthermore, we study the asymptotic distribution of the dimension of the j-th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced in [Linial and Meshulam, Combinatorica, 2006], a result which has only been known for dimension two [Kahle and Pittel, Random Structures Algorithms, 2016].
Cite as

Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel. Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooley_et_al:LIPIcs.AofA.2018.7,
  author =	{Cooley, Oliver and Del Giudice, Nicola and Kang, Mihyun and Spr\"{u}ssel, Philipp},
  title =	{{Vanishing of Cohomology Groups of Random Simplicial Complexes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.7},
  URN =		{urn:nbn:de:0030-drops-89006},
  doi =		{10.4230/LIPIcs.AofA.2018.7},
  annote =	{Keywords: Random hypergraphs, random simplicial complexes, sharp threshold, hitting time, connectedness}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.17
The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property

Authors: Chris Dowden, Mihyun Kang, and Michael Krivelevich

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We investigate the genus g(n,m) of the Erdös-Rényi random graph G(n,m), providing a thorough description of how this relates to the function m=m(n), and finding that there is different behaviour depending on which `region' m falls into. Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases. In particular, we show that g(n,m) = (1+o(1)) m/(2) whp (with high probability) when n << m = n^{1+o(1)}; that g(n,m) = (1+o(1)) mu (lambda) m whp for a given function mu (lambda) when m ~ lambda n for lambda > 1/2; and that g(n,m) = (1+o(1)) (8s^3)/(3n^2) whp when m = n/(2) + s for n^(2/3) << s << n. We then also show that the genus of fixed graphs can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of epsilon n edges will whp result in a graph with genus Omega (n), even when epsilon is an arbitrarily small constant! We thus call this the `fragile genus' property.
Cite as

Chris Dowden, Mihyun Kang, and Michael Krivelevich. The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dowden_et_al:LIPIcs.AofA.2018.17,
  author =	{Dowden, Chris and Kang, Mihyun and Krivelevich, Michael},
  title =	{{The Genus of the Erd\"{o}s-R\'{e}nyi Random Graph and the Fragile Genus Property}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.17},
  URN =		{urn:nbn:de:0030-drops-89100},
  doi =		{10.4230/LIPIcs.AofA.2018.17},
  annote =	{Keywords: Random graphs, Genus, Fragile genus}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.29
Asymptotic Expansions for Sub-Critical Lagrangean Forms

Authors: Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
Asymptotic expansions for the Taylor coefficients of the Lagrangean form phi(z)=zf(phi(z)) are examined with a focus on the calculations of the asymptotic coefficients. The expansions are simple and useful, and we discuss their use in some enumerating sequences in trees, lattice paths and planar maps.
Cite as

Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh. Asymptotic Expansions for Sub-Critical Lagrangean Forms. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hwang_et_al:LIPIcs.AofA.2018.29,
  author =	{Hwang, Hsien-Kuei and Kang, Mihyun and Duh, Guan-Huei},
  title =	{{Asymptotic Expansions for Sub-Critical Lagrangean Forms}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.29},
  URN =		{urn:nbn:de:0030-drops-89224},
  doi =		{10.4230/LIPIcs.AofA.2018.29},
  annote =	{Keywords: asymptotic expansions, Lagrangean forms, saddle-point method, singularity analysis, maps}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.40
Charting the Replica Symmetric Phase

Authors: Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, and Tobias Kapetanopoulos

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
Random graph models and associated inference problems such as the stochastic block model play an eminent role in computer science, discrete mathematics and statistics. Based on non-rigorous arguments physicists predicted the existence of a generic phase transition that separates a "replica symmetric phase" where statistical inference is impossible from a phase where the detection of the "ground truth" is information-theoretically possible. In this paper we prove a contiguity result that shows that detectability is indeed impossible within the replica-symmetric phase for a broad class of models. In particular, this implies the detectability conjecture for the disassortative stochastic block model from [Decelle et al.: Phys Rev E 2011]. Additionally, we investigate key features of the replica symmetric phase such as the nature of point-to-set correlations (`reconstruction').
Cite as

Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, and Tobias Kapetanopoulos. Charting the Replica Symmetric Phase. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2017.40,
  author =	{Coja-Oghlan, Amin and Efthymiou, Charilaos and Jaafari, Nor and Kang, Mihyun and Kapetanopoulos, Tobias},
  title =	{{Charting the Replica Symmetric Phase}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.40},
  URN =		{urn:nbn:de:0030-drops-75895},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.40},
  annote =	{Keywords: Random factor graph, bounds for condensation phase transition, Potts antiferromagnet, diluted k-spin model, stochastic block model}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.710
The Minimum Bisection in the Planted Bisection Model

Authors: Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
In the planted bisection model a random graph G(n,p_+,p_-) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to plus or minus 1). Any two vertices that belong to the same class are linked by an edge with probability p_+ and any two that belong to different classes with probability (p_-) <(p_+) independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If (p_+)=2(d_+)/n and (p_-)=2(d_-)/n for numbers 0 <= (d_-) <(d_+) that remain fixed as n tends to infinity, then with high probability the "planted" bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that (d_+)-(d_-) > c * sqrt((d_+)ln(d_+)) for a certain constant c>0.
Cite as

Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch. The Minimum Bisection in the Planted Bisection Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 710-725, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2015.710,
  author =	{Coja-Oghlan, Amin and Cooley, Oliver and Kang, Mihyun and Skubch, Kathrin},
  title =	{{The Minimum Bisection in the Planted Bisection Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{710--725},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  URN =		{urn:nbn:de:0030-drops-53315},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  annote =	{Keywords: Random graphs, minimum bisection, planted bisection, belief propagation.}
}

Feng, Yuan

Document
DOI: 10.4230/LIPIcs.CONCUR.2017.35
Model Checking Omega-regular Properties for Quantum Markov Chains

Authors: Yuan Feng, Ernst Moritz Hahn, Andrea Turrini, and Shenggang Ying

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
Quantum Markov chains are an extension of classical Markov chains which are labelled with super-operators rather than probabilities. They allow to faithfully represent quantum programs and quantum protocols. In this paper, we investigate model checking omega-regular properties, a very general class of properties (including, e.g., LTL properties) of interest, against this model. For classical Markov chains, such properties are usually checked by building the product of the model with a language automaton. Subsequent analysis is then performed on this product. When doing so, one takes into account its graph structure, and for instance performs different analyses per bottom strongly connected component (BSCC). Unfortunately, for quantum Markov chains such an approach does not work directly, because super-operators behave differently from probabilities. To overcome this problem, we transform the product quantum Markov chain into a single super-operator, which induces a decomposition of the state space (the tensor product of classical state space and the quantum one) into a family of BSCC subspaces. Interestingly, we show that this BSCC decomposition provides a solution to the issue of model checking omega-regular properties for quantum Markov chains.
Cite as

Yuan Feng, Ernst Moritz Hahn, Andrea Turrini, and Shenggang Ying. Model Checking Omega-regular Properties for Quantum Markov Chains. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.CONCUR.2017.35,
  author =	{Feng, Yuan and Hahn, Ernst Moritz and Turrini, Andrea and Ying, Shenggang},
  title =	{{Model Checking Omega-regular Properties for Quantum Markov Chains}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.35},
  URN =		{urn:nbn:de:0030-drops-77818},
  doi =		{10.4230/LIPIcs.CONCUR.2017.35},
  annote =	{Keywords: Quantum Markov chains, model checking, omega-regular properties, bottom strongly connected component}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.427
On Coinduction and Quantum Lambda Calculi

Authors: Yuxin Deng, Yuan Feng, and Ugo Dal Lago

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
In the ubiquitous presence of linear resources in quantum computation, program equivalence in linear contexts, where programs are used or executed once, is more important than in the classical setting. We introduce a linear contextual equivalence and two notions of bisimilarity, a state-based and a distribution-based, as proof techniques for reasoning about higher-order quantum programs. Both notions of bisimilarity are sound with respect to the linear contextual equivalence, but only the distribution-based one turns out to be complete. The completeness proof relies on a characterisation of the bisimilarity as a testing equivalence.
Cite as

Yuxin Deng, Yuan Feng, and Ugo Dal Lago. On Coinduction and Quantum Lambda Calculi. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 427-440, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.CONCUR.2015.427,
  author =	{Deng, Yuxin and Feng, Yuan and Dal Lago, Ugo},
  title =	{{On Coinduction and Quantum Lambda Calculi}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{427--440},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.427},
  URN =		{urn:nbn:de:0030-drops-53883},
  doi =		{10.4230/LIPIcs.CONCUR.2015.427},
  annote =	{Keywords: Quantum lambda calculi, contextual equivalence, bisimulation}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.441
Toward Automatic Verification of Quantum Cryptographic Protocols

Authors: Yuan Feng and Mingsheng Ying

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
Several quantum process algebras have been proposed and successfully applied in verification of quantum cryptographic protocols. All of the bisimulations proposed so far for quantum processes in these process algebras are state-based, implying that they only compare individual quantum states, but not a combination of them. This paper remedies this problem by introducing a novel notion of distribution-based bisimulation for quantum processes. We further propose an approximate version of this bisimulation that enables us to prove more sophisticated security properties of quantum protocols which cannot be verified using the previous bisimulations. In particular, we prove that the quantum key distribution protocol BB84 is sound and (asymptotically) secure against the intercept-resend attacks by showing that the BB84 protocol, when executed with such an attacker concurrently, is approximately bisimilar to an ideal protocol, whose soundness and security are obviously guaranteed, with at most an exponentially decreasing gap.
Cite as

Yuan Feng and Mingsheng Ying. Toward Automatic Verification of Quantum Cryptographic Protocols. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 441-455, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.CONCUR.2015.441,
  author =	{Feng, Yuan and Ying, Mingsheng},
  title =	{{Toward Automatic Verification of Quantum Cryptographic Protocols}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{441--455},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.441},
  URN =		{urn:nbn:de:0030-drops-53936},
  doi =		{10.4230/LIPIcs.CONCUR.2015.441},
  annote =	{Keywords: Quantum cryptographic protocols, Verification, Bisimulation, Security}
}

Feng, Zhe

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.13
The Average-Value Allocation Problem

Authors: Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, and Di Wang

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of e/(e-1), and provide a 4e/(e-1)-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm.
Cite as

Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, and Di Wang. The Average-Value Allocation Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhawalkar_et_al:LIPIcs.APPROX/RANDOM.2024.13,
  author =	{Bhawalkar, Kshipra and Feng, Zhe and Gupta, Anupam and Mehta, Aranyak and Wajc, David and Wang, Di},
  title =	{{The Average-Value Allocation Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.13},
  URN =		{urn:nbn:de:0030-drops-210062},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.13},
  annote =	{Keywords: Resource allocation, return-on-spend constraint, approximation algorithm, online algorithm}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.23
Understanding PPA-Completeness

Authors: Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We consider the problem of finding a fully colored base triangle on the 2-dimensional Möbius band under the standard boundary condition, proving it to be PPA-complete. The proof is based on a construction for the DPZP problem, that of finding a zero point under a discrete version of continuity condition. It further derives PPA-completeness for versions on the Möbius band of other related discrete fixed point type problems, and a special version of the Tucker problem, finding an edge such that if the value of one end vertex is x, the other is -x, given a special anti-symmetry boundary condition. More generally, this applies to other non-orientable spaces, including the projective plane and the Klein bottle. However, since those models have a closed boundary, we rely on a version of the PPA that states it as to find another fixed point giving a fixed point. This model also makes it presentationally simple for an extension to a high dimensional discrete fixed point problem on a non-orientable (nearly) hyper-grid with a constant side length.
Cite as

Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu. Understanding PPA-Completeness. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 23:1-23:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.CCC.2016.23,
  author =	{Deng, Xiaotie and Edmonds, Jack R. and Feng, Zhe and Liu, Zhengyang and Qi, Qi and Xu, Zeying},
  title =	{{Understanding PPA-Completeness}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{23:1--23:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.23},
  URN =		{urn:nbn:de:0030-drops-58310},
  doi =		{10.4230/LIPIcs.CCC.2016.23},
  annote =	{Keywords: Fixed Point Computation, PPA-Completeness}
}

Feng, Qilong

Document
DOI: 10.4230/LIPIcs.MFCS.2024.84
Faster Approximation Schemes for (Constrained) k-Means with Outliers

Authors: Zhen Zhang, Junyu Huang, and Qilong Feng

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a set of n points in ℝ^d and two positive integers k and m, the Euclidean k-means with outliers problem aims to remove at most m points, referred to as outliers, and minimize the k-means cost function for the remaining points. Developing algorithms for this problem remains an active area of research due to its prevalence in applications involving noisy data. In this paper, we give a (1+ε)-approximation algorithm that runs in n²d((k+m)ε^{-1})^O(kε^{-1}) time for the problem. When combined with a coreset construction method, the running time of the algorithm can be improved to be linear in n. For the case where k is a constant, this represents the first polynomial-time approximation scheme for the problem: Existing algorithms with the same approximation guarantee run in polynomial time only when both k and m are constants. Furthermore, our approach generalizes to variants of k-means with outliers incorporating additional constraints on instances, such as those related to capacities and fairness.
Cite as

Zhen Zhang, Junyu Huang, and Qilong Feng. Faster Approximation Schemes for (Constrained) k-Means with Outliers. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 84:1-84:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.MFCS.2024.84,
  author =	{Zhang, Zhen and Huang, Junyu and Feng, Qilong},
  title =	{{Faster Approximation Schemes for (Constrained) k-Means with Outliers}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{84:1--84:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.84},
  URN =		{urn:nbn:de:0030-drops-206408},
  doi =		{10.4230/LIPIcs.MFCS.2024.84},
  annote =	{Keywords: Approximation algorithms, clustering}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.5
A Unified Framework of FPT Approximation Algorithms for Clustering Problems

Authors: Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In this paper, we present a framework for designing FPT approximation algorithms for many k-clustering problems. Our results are based on a new technique for reducing search spaces. A reduced search space is a small subset of the input data that has the guarantee of containing k clients close to the facilities opened in an optimal solution for any clustering problem we consider. We show, somewhat surprisingly, that greedily sampling O(k) clients yields the desired reduced search space, based on which we obtain FPT(k)-time algorithms with improved approximation guarantees for problems such as capacitated clustering, lower-bounded clustering, clustering with service installation costs, fault tolerant clustering, and priority clustering.
Cite as

Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. A Unified Framework of FPT Approximation Algorithms for Clustering Problems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ISAAC.2020.5,
  author =	{Feng, Qilong and Zhang, Zhen and Huang, Ziyun and Xu, Jinhui and Wang, Jianxin},
  title =	{{A Unified Framework of FPT Approximation Algorithms for Clustering Problems}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.5},
  URN =		{urn:nbn:de:0030-drops-133495},
  doi =		{10.4230/LIPIcs.ISAAC.2020.5},
  annote =	{Keywords: clustering, approximation algorithms, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.26
Small Candidate Set for Translational Pattern Search

Authors: Ziyun Huang, Qilong Feng, Jianxin Wang, and Jinhui Xu

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

Abstract
In this paper, we study the following pattern search problem: Given a pair of point sets A and B in fixed dimensional space R^d, with |B| = n, |A| = m and n >= m, the pattern search problem is to find the translations T’s of A such that each of the identified translations induces a matching between T(A) and a subset B' of B with cost no more than some given threshold, where the cost is defined as the minimum bipartite matching cost of T(A) and B'. We present a novel algorithm to produce a small set of candidate translations for the pattern search problem. For any B' subseteq B with |B'| = |A|, there exists at least one translation T in the candidate set such that the minimum bipartite matching cost between T(A) and B' is no larger than (1+epsilon) times the minimum bipartite matching cost between A and B' under any translation (i.e., the optimal translational matching cost). We also show that there exists an alternative solution to this problem, which constructs a candidate set of size O(n log^2 n) in O(n log^2 n) time with high probability of success. As a by-product of our construction, we obtain a weak epsilon-net for hypercube ranges, which significantly improves the construction time and the size of the candidate set. Our technique can be applied to a number of applications, including the translational pattern matching problem.
Cite as

Ziyun Huang, Qilong Feng, Jianxin Wang, and Jinhui Xu. Small Candidate Set for Translational Pattern Search. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ISAAC.2019.26,
  author =	{Huang, Ziyun and Feng, Qilong and Wang, Jianxin and Xu, Jinhui},
  title =	{{Small Candidate Set for Translational Pattern Search}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{26:1--26:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.26},
  URN =		{urn:nbn:de:0030-drops-115222},
  doi =		{10.4230/LIPIcs.ISAAC.2019.26},
  annote =	{Keywords: Bipartite matching, Alignment, Discretization, Approximate algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.61
Improved Algorithms for Clustering with Outliers

Authors: Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang

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

Abstract
Clustering is a fundamental problem in unsupervised learning. In many real-world applications, the to-be-clustered data often contains various types of noises and thus needs to be removed from the learning process. To address this issue, we consider in this paper two variants of such clustering problems, called k-median with m outliers and k-means with m outliers. Existing techniques for both problems either incur relatively large approximation ratios or can only efficiently deal with a small number of outliers. In this paper, we present improved solution to each of them for the case where k is a fixed number and m could be quite large. Particularly, we gave the first PTAS for the k-median problem with outliers in Euclidean space R^d for possibly high m and d. Our algorithm runs in O(nd((1/epsilon)(k+m))^(k/epsilon)^O(1)) time, which considerably improves the previous result (with running time O(nd(m+k)^O(m+k) + (1/epsilon)k log n)^O(1))) given by [Feldman and Schulman, SODA 2012]. For the k-means with outliers problem, we introduce a (6+epsilon)-approximation algorithm for general metric space with running time O(n(beta (1/epsilon)(k+m))^k) for some constant beta>1. Our algorithm first uses the k-means++ technique to sample O((1/epsilon)(k+m)) points from input and then select the k centers from them. Compared to the more involving existing techniques, our algorithms are much simpler, i.e., using only random sampling, and achieving better performance ratios.
Cite as

Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. Improved Algorithms for Clustering with Outliers. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ISAAC.2019.61,
  author =	{Feng, Qilong and Zhang, Zhen and Huang, Ziyun and Xu, Jinhui and Wang, Jianxin},
  title =	{{Improved Algorithms for Clustering with Outliers}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{61:1--61:12},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.61},
  URN =		{urn:nbn:de:0030-drops-115573},
  doi =		{10.4230/LIPIcs.ISAAC.2019.61},
  annote =	{Keywords: Clustering with Outliers, Approximation, Random Sampling}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.31
New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition

Authors: Qilong Feng, Guanlan Tan, Senmin Zhu, Bin Fu, and Jianxin Wang

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
König-Egerváry graphs form an important graph class which has been studied extensively in graph theory. Much attention has also been paid on König-Egerváry subgraphs and König-Egerváry graph modification problems. In this paper, we focus on one König-Egerváry subgraph problem, called the Maximum Edge Induced König Subgraph problem. By exploiting the classical Gallai-Edmonds decomposition, we establish connections between minimum vertex cover, Gallai-Edmonds decomposition structure, maximum matching, maximum bisection, and König-Egerváry subgraph structure. We obtain a new structural property of König-Egerváry subgraph: every graph G=(V, E) has an edge induced König-Egerváry subgraph with at least 2|E|/3 edges. Based on the new structural property proposed, an approximation algorithm with ratio 10/7 for the Maximum Edge Induced König Subgraph problem is presented, improving the current best ratio of 5/3. To the best of our knowledge, this paper is the first one establishing the connection between Gallai-Edmonds decomposition and König-Egerváry graphs. Using 2|E|/3 as a lower bound, we define the Edge Induced König Subgraph above lower bound problem, and give a kernel of at most 30k edges for the problem.
Cite as

Qilong Feng, Guanlan Tan, Senmin Zhu, Bin Fu, and Jianxin Wang. New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 31:1-31:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ISAAC.2018.31,
  author =	{Feng, Qilong and Tan, Guanlan and Zhu, Senmin and Fu, Bin and Wang, Jianxin},
  title =	{{New Algorithms for Edge Induced K\"{o}nig-Egerv\'{a}ry Subgraph Based on Gallai-Edmonds Decomposition}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{31:1--31:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.31},
  URN =		{urn:nbn:de:0030-drops-99790},
  doi =		{10.4230/LIPIcs.ISAAC.2018.31},
  annote =	{Keywords: K\"{o}nig-Egerv\'{a}ry graph, Gallai-Edmonds decomposition}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.65
An Improved FPT Algorithm for the Flip Distance Problem

Authors: Shaohua Li, Qilong Feng, Xiangzhong Meng, and Jianxin Wang

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Given a set \cal P of points in the Euclidean plane and two triangulations of \cal P, the flip distance between these two triangulations is the minimum number of flips required to transform one triangulation into the other. The Parameterized Flip Distance problem is to decide if the flip distance between two given triangulations is equal to a given integer k. The previous best FPT algorithm runs in time O^*(k\cdot c^k) (c\leq 2\times 14^11), where each step has fourteen possible choices, and the length of the action sequence is bounded by 11k. By applying the backtracking strategy and analyzing the underlying property of the flip sequence, each step of our algorithm has only five possible choices. Based on an auxiliary graph G, we prove that the length of the action sequence for our algorithm is bounded by 2|G|. As a result, we present an FPT algorithm running in time O^*(k\cdot 32^k).
Cite as

Shaohua Li, Qilong Feng, Xiangzhong Meng, and Jianxin Wang. An Improved FPT Algorithm for the Flip Distance Problem. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.MFCS.2017.65,
  author =	{Li, Shaohua and Feng, Qilong and Meng, Xiangzhong and Wang, Jianxin},
  title =	{{An Improved FPT Algorithm for the Flip Distance Problem}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.65},
  URN =		{urn:nbn:de:0030-drops-81100},
  doi =		{10.4230/LIPIcs.MFCS.2017.65},
  annote =	{Keywords: triangulation, flip distance, FPT algorithm}
}

Feng, Haodi

Document
DOI: 10.4230/LIPIcs.CPM.2018.14
Can a permutation be sorted by best short swaps?

Authors: Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo, and Haodi Feng

Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

Abstract
A short swap switches two elements with at most one element caught between them. Sorting permutation by short swaps asks to find a shortest short swap sequence to transform a permutation into another. A short swap can eliminate at most three inversions. It is still open for whether a permutation can be sorted by short swaps each of which can eliminate three inversions. In this paper, we present a polynomial time algorithm to solve the problem, which can decide whether a permutation can be sorted by short swaps each of which can eliminate 3 inversions in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time, where n is the number of elements in the permutation. A short swap can cause the total length of two element vectors to decrease by at most 4. We further propose an algorithm to recognize a permutation which can be sorted by short swaps each of which can cause the element vector length sum to decrease by 4 in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time. This improves upon the O(n^2) algorithm proposed by Heath and Vergara to decide whether a permutation is so called lucky.
Cite as

Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo, and Haodi Feng. Can a permutation be sorted by best short swaps?. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.CPM.2018.14,
  author =	{Zhang, Shu and Zhu, Daming and Jiang, Haitao and Ma, Jingjing and Guo, Jiong and Feng, Haodi},
  title =	{{Can a permutation be sorted by best short swaps?}},
  booktitle =	{29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Navarro, Gonzalo and Sankoff, David and Zhu, Binhai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.14},
  URN =		{urn:nbn:de:0030-drops-86957},
  doi =		{10.4230/LIPIcs.CPM.2018.14},
  annote =	{Keywords: Algorithm, Complexity, Short Swap, Permutation, Reversal}
}

Feng, Xin

Document
DOI: 10.4230/LIPIcs.GISCIENCE.2018.12
Heterogeneous Skeleton for Summarizing Continuously Distributed Demand in a Region

Authors: Alan T. Murray, Xin Feng, and Ali Shokoufandeh

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

Abstract
There has long been interest in the skeleton of a spatial object in GIScience. The reasons for this are many, as it has proven to be an extremely useful summary and explanatory representation of complex objects. While much research has focused on issues of computational complexity and efficiency in extracting the skeletal and medial axis representations as well as interpreting the final product, little attention has been paid to fundamental assumptions about the underlying object. This paper discusses the implied assumption of homogeneity associated with methods for deriving a skeleton. Further, it is demonstrated that addressing heterogeneity complicates both the interpretation and identification of a meaningful skeleton. The heterogeneous skeleton is introduced and formalized, along with a method for its identification. Application results are presented to illustrate the heterogeneous skeleton and provides comparative contrast to homogeneity assumptions.
Cite as

Alan T. Murray, Xin Feng, and Ali Shokoufandeh. Heterogeneous Skeleton for Summarizing Continuously Distributed Demand in a Region. In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{murray_et_al:LIPIcs.GISCIENCE.2018.12,
  author =	{Murray, Alan T. and Feng, Xin and Shokoufandeh, Ali},
  title =	{{Heterogeneous Skeleton for Summarizing Continuously Distributed Demand in a Region}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{12:1--12:11},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.12},
  URN =		{urn:nbn:de:0030-drops-93400},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.12},
  annote =	{Keywords: Medial axis, Object center, Geographical summary, Spatial analytics}
}

Kang, Chaogui

Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.38
An Analytical Framework for Understanding Urban Functionality from Human Activities (Short Paper)

Authors: Chaogui Kang and Yu Liu

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

Abstract
The intertwined relationship between urban functionality and human activity has been widely recognized and quantified with the assistance of big geospatial data. In specific, urban land uses as an important facet of urban structure can be identified from spatiotemporal patterns of aggregate human activities. In this article, we propose a space, time and activity cuboid based analytical framework for clustering urban spaces into different categories of urban functionality based on the variation of activity intensity (T-fiber), mixture (A-fiber) and interaction (I- and O-fiber). The ability of the proposed framework is empirically evaluated by three case studies.
Cite as

Chaogui Kang and Yu Liu. An Analytical Framework for Understanding Urban Functionality from Human Activities (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 38:1-38:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kang_et_al:LIPIcs.GISCIENCE.2018.38,
  author =	{Kang, Chaogui and Liu, Yu},
  title =	{{An Analytical Framework for Understanding Urban Functionality from Human Activities}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{38:1--38:8},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.38},
  URN =		{urn:nbn:de:0030-drops-93668},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.38},
  annote =	{Keywords: Urban functionality, Human activity, STA cuboid, Spatiotemporal distribution, Clustering}
}

Kang, Ning

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.14
Online Makespan Minimization: The Power of Restart

Authors: Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of (5 - sqrt{5})/2 ~~ 1.382, matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios. We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case.
Cite as

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online Makespan Minimization: The Power of Restart. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2018.14,
  author =	{Huang, Zhiyi and Kang, Ning and Tang, Zhihao Gavin and Wu, Xiaowei and Zhang, Yuhao},
  title =	{{Online Makespan Minimization: The Power of Restart}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.14},
  URN =		{urn:nbn:de:0030-drops-94182},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.14},
  annote =	{Keywords: Online Scheduling, Makespan Minimization, Identical Machines}
}

Kang, Yuhao

Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.41
Understanding Place Identity with Generative AI (Short Paper)

Authors: Kee Moon Jang, Junda Chen, Yuhao Kang, Junghwan Kim, Jinhyung Lee, and Fábio Duarte

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Researchers are constantly leveraging new forms of data to understand how people perceive the built environment and the collective place identity of cities. Latest advancements in generative artificial intelligence (AI) models have enabled the creation of realistic representations of real-world settings. In this study, we explore the potential of generative AI as the source of textual and visual information in capturing the place identity of cities assessed by filtered descriptions and images. We asked questions on the place identity of a set of 31 global cities to two generative AI models, ChatGPT and DALL·E2. Since generative AI has raised ethical concerns regarding its trustworthiness, we performed cross-validation to examine whether the results show similar patterns to real urban settings. In particular, we compared the outputs with Wikipedia data for text and images searched from Google for images. Our results indicate that generative AI models have the potential to capture the collective features of cities that can make them distinguishable. This study is among the first attempts to explore the capabilities of generative AI in understanding human perceptions of the built environment. It contributes to urban design literature by discussing future research opportunities and potential limitations.
Cite as

Kee Moon Jang, Junda Chen, Yuhao Kang, Junghwan Kim, Jinhyung Lee, and Fábio Duarte. Understanding Place Identity with Generative AI (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 41:1-41:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jang_et_al:LIPIcs.GIScience.2023.41,
  author =	{Jang, Kee Moon and Chen, Junda and Kang, Yuhao and Kim, Junghwan and Lee, Jinhyung and Duarte, F\'{a}bio},
  title =	{{Understanding Place Identity with Generative AI}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{41:1--41:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.41},
  URN =		{urn:nbn:de:0030-drops-189363},
  doi =		{10.4230/LIPIcs.GIScience.2023.41},
  annote =	{Keywords: ChatGPT, DALL·E2, place identity, generative artificial intelligence, sense of place}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.93
The Ethics of AI-Generated Maps: DALL·E 2 and AI’s Implications for Cartography (Short Paper)

Authors: Qianheng Zhang, Yuhao Kang, and Robert Roth

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
The rapid advancement of artificial intelligence (AI) such as the emergence of large language models ChatGPT and DALL·E 2 has brought both opportunities for improving productivity and raised ethical concerns. This paper investigates the ethics of using artificial intelligence (AI) in cartography, with a particular focus on the generation of maps using DALL·E 2. To accomplish this, we first created an open-sourced dataset that includes synthetic (AI-generated) and real-world (human-designed) maps at multiple scales with a variety of settings. We subsequently examined four potential ethical concerns that may arise from the characteristics of DALL·E 2 generated maps, namely inaccuracies, misleading information, unanticipated features, and irreproducibility. We then developed a deep learning-based model to identify those AI-generated maps. Our research emphasizes the importance of ethical considerations in the development and use of AI techniques in cartography, contributing to the growing body of work on trustworthy maps. We aim to raise public awareness of the potential risks associated with AI-generated maps and support the development of ethical guidelines for their future use.
Cite as

Qianheng Zhang, Yuhao Kang, and Robert Roth. The Ethics of AI-Generated Maps: DALL·E 2 and AI’s Implications for Cartography (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 93:1-93:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.GIScience.2023.93,
  author =	{Zhang, Qianheng and Kang, Yuhao and Roth, Robert},
  title =	{{The Ethics of AI-Generated Maps: DALL·E 2 and AI’s Implications for Cartography}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{93:1--93:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.93},
  URN =		{urn:nbn:de:0030-drops-189886},
  doi =		{10.4230/LIPIcs.GIScience.2023.93},
  annote =	{Keywords: Ethics, GeoAI, DALL-E, Cartography}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.12
LSTM-TrajGAN: A Deep Learning Approach to Trajectory Privacy Protection

Authors: Jinmeng Rao, Song Gao, Yuhao Kang, and Qunying Huang

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Abstract
The prevalence of location-based services contributes to the explosive growth of individual-level trajectory data and raises public concerns about privacy issues. In this research, we propose a novel LSTM-TrajGAN approach, which is an end-to-end deep learning model to generate privacy-preserving synthetic trajectory data for data sharing and publication. We design a loss metric function TrajLoss to measure the trajectory similarity losses for model training and optimization. The model is evaluated on the trajectory-user-linking task on a real-world semantic trajectory dataset. Compared with other common geomasking methods, our model can better prevent users from being re-identified, and it also preserves essential spatial, temporal, and thematic characteristics of the real trajectory data. The model better balances the effectiveness of trajectory privacy protection and the utility for spatial and temporal analyses, which offers new insights into the GeoAI-powered privacy protection.
Cite as

Jinmeng Rao, Song Gao, Yuhao Kang, and Qunying Huang. LSTM-TrajGAN: A Deep Learning Approach to Trajectory Privacy Protection. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rao_et_al:LIPIcs.GIScience.2021.I.12,
  author =	{Rao, Jinmeng and Gao, Song and Kang, Yuhao and Huang, Qunying},
  title =	{{LSTM-TrajGAN: A Deep Learning Approach to Trajectory Privacy Protection}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.12},
  URN =		{urn:nbn:de:0030-drops-130471},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.12},
  annote =	{Keywords: GeoAI, Deep Learning, Trajectory Privacy, Generative Adversarial Networks}
}

Feng, Weiming

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.11
Approximate Counting for Spin Systems in Sub-Quadratic Time

Authors: Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, and Jiaheng Wang

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We present two randomised approximate counting algorithms with Õ(n^{2-c}/ε²) running time for some constant c > 0 and accuracy ε: 1) for the hard-core model with fugacity λ on graphs with maximum degree Δ when λ = O(Δ^{-1.5-c₁}) where c₁ = c/(2-2c); 2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as ℤ². For the hard-core model, Weitz’s algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when λ = o(Δ^{-2}). Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as ℤ^d, but with a running time of the form Õ(n²ε^{-2}/2^{c(log n)^{1/d}}) where d is the exponent of the polynomial growth and c > 0 is some constant.
Cite as

Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, and Jiaheng Wang. Approximate Counting for Spin Systems in Sub-Quadratic Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.ICALP.2024.11,
  author =	{Anand, Konrad and Feng, Weiming and Freifeld, Graham and Guo, Heng and Wang, Jiaheng},
  title =	{{Approximate Counting for Spin Systems in Sub-Quadratic Time}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.11},
  URN =		{urn:nbn:de:0030-drops-201543},
  doi =		{10.4230/LIPIcs.ICALP.2024.11},
  annote =	{Keywords: Randomised algorithm, Approximate counting, Spin system, Sub-quadratic algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.62
An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs

Authors: Weiming Feng and Heng Guo

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs (DAGs). In contrast, we also show the complementing problem of approximating two terminal unreliability in DAGs is #BIS-hard.
Cite as

Weiming Feng and Heng Guo. An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2024.62,
  author =	{Feng, Weiming and Guo, Heng},
  title =	{{An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.62},
  URN =		{urn:nbn:de:0030-drops-202057},
  doi =		{10.4230/LIPIcs.ICALP.2024.62},
  annote =	{Keywords: Approximate counting, Network reliability, Sampling algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.54
On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)

Authors: Charilaos Efthymiou and Weiming Feng

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the single-site Glauber dynamics for the fugacity λ, Hard-Core model on the random graph G(n, d/n). We show that for the typical instances of the random graph G(n,d/n) and for fugacity λ < {d^d} / {(d-1)^(d+1)}, the mixing time of Glauber dynamics is n^{1 + O(1/log log n)}. Our result improves on the recent elegant algorithm in [Bezáková, Galanis, Goldberg and Štefankovič; ICALP'22]. The algorithm there is an MCMC-based sampling algorithm, but it is not the Glauber dynamics. Our algorithm here is simpler, as we use the classic Glauber dynamics. Furthermore, the bounds on mixing time we prove are smaller than those in Bezáková et al. paper, hence our algorithm is also faster. The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for G(n,d/n). As corollary of our analysis for the Hard-Core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-Dimer model on G(n,d/n). The bounds we get for this model are slightly better than those we have for the Hard-Core model
Cite as

Charilaos Efthymiou and Weiming Feng. On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{efthymiou_et_al:LIPIcs.ICALP.2023.54,
  author =	{Efthymiou, Charilaos and Feng, Weiming},
  title =	{{On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.54},
  URN =		{urn:nbn:de:0030-drops-181064},
  doi =		{10.4230/LIPIcs.ICALP.2023.54},
  annote =	{Keywords: spin-system, spin-glass, sparse random (hyper)graph, approximate sampling, efficient algorithm}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.25
Improved Bounds for Randomly Colouring Simple Hypergraphs

Authors: Weiming Feng, Heng Guo, and Jiaheng Wang

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ > 0, if k ≥ 20(1+δ)/δ and q ≥ 100Δ^({2+δ}/{k-4/δ-4}), the running time of our algorithm is Õ(poly(Δ k)⋅ n^1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Vuong, 2021; He, Sun, and Wu, 2021), and does not require Ω(log n) colours unlike the work of Frieze and Anastos (2017).
Cite as

Weiming Feng, Heng Guo, and Jiaheng Wang. Improved Bounds for Randomly Colouring Simple Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.APPROX/RANDOM.2022.25,
  author =	{Feng, Weiming and Guo, Heng and Wang, Jiaheng},
  title =	{{Improved Bounds for Randomly Colouring Simple Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.25},
  URN =		{urn:nbn:de:0030-drops-171477},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.25},
  annote =	{Keywords: Approximate counting, Markov chain, Mixing time, Hypergraph colouring}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.25
Dynamic Inference in Probabilistic Graphical Models

Authors: Weiming Feng, Kun He, Xiaoming Sun, and Yitong Yin

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Probabilistic graphical models, such as Markov random fields (MRFs), are useful for describing high-dimensional distributions in terms of local dependence structures. The {probabilistic inference} is a fundamental problem related to graphical models, and sampling is a main approach for the problem. In this paper, we study probabilistic inference problems when the graphical model itself is changing dynamically with time. Such dynamic inference problems arise naturally in today’s application, e.g. multivariate time-series data analysis and practical learning procedures. We give a dynamic algorithm for sampling-based probabilistic inferences in MRFs, where each dynamic update can change the underlying graph and all parameters of the MRF simultaneously, as long as the total amount of changes is bounded. More precisely, suppose that the MRF has n variables and polylogarithmic-bounded maximum degree, and N(n) independent samples are sufficient for the inference for a polynomial function N(⋅). Our algorithm dynamically maintains an answer to the inference problem using Õ(n N(n)) space cost, and Õ(N(n) + n) incremental time cost upon each update to the MRF, as long as the Dobrushin-Shlosman condition is satisfied by the MRFs. This well-known condition has long been used for guaranteeing the efficiency of Markov chain Monte Carlo (MCMC) sampling in the traditional static setting. Compared to the static case, which requires Ω(n N(n)) time cost for redrawing all N(n) samples whenever the MRF changes, our dynamic algorithm gives a 𝛺^~(min{n, N(n)})-factor speedup. Our approach relies on a novel dynamic sampling technique, which transforms local Markov chains (a.k.a. single-site dynamics) to dynamic sampling algorithms, and an "algorithmic Lipschitz" condition that we establish for sampling from graphical models, namely, when the MRF changes by a small difference, samples can be modified to reflect the new distribution, with cost proportional to the difference on MRF.
Cite as

Weiming Feng, Kun He, Xiaoming Sun, and Yitong Yin. Dynamic Inference in Probabilistic Graphical Models. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ITCS.2021.25,
  author =	{Feng, Weiming and He, Kun and Sun, Xiaoming and Yin, Yitong},
  title =	{{Dynamic Inference in Probabilistic Graphical Models}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.25},
  URN =		{urn:nbn:de:0030-drops-135643},
  doi =		{10.4230/LIPIcs.ITCS.2021.25},
  annote =	{Keywords: Dynamic inference, probabilistic graphical model, Gibbs sampling, Markov random filed}
}

Feng, Yiding

Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2021.88
Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)

Authors: Yiding Feng and Rad Niazadeh

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
In several applications of real-time matching of demand to supply in online marketplaces, the platform can allow for some latency to batch the demand and improve the matching’s efficiency. Motivated by these scenarios, we study the optimal trade-off between batching and inefficiency in online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems, where online vertices arrive in K batches. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratios known for the online variant of these problems [Mehta et al., 2007; Aggarwal et al., 2011]. Our main technique is using a family of convex-programming based matchings that distribute the demand in a particularly balanced way among supply in different stages. More precisely, we identify a sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers of the optimal matching linear program to form this family. By providing structural decompositions of the underlying graph using the optimal solutions of these convex programs, we develop a new multi-stage primal-dual framework to analyze the fractional multi-stage algorithm that returns the corresponding regularized optimal matching in each stage (by solving the stage’s convex program). We further show a matching upper-bound by providing an unweighted instance of the problem in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios.
Cite as

Yiding Feng and Rad Niazadeh. Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, p. 88:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ITCS.2021.88,
  author =	{Feng, Yiding and Niazadeh, Rad},
  title =	{{Batching and Optimal Multi-Stage Bipartite Allocations}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{88:1--88:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.88},
  URN =		{urn:nbn:de:0030-drops-136272},
  doi =		{10.4230/LIPIcs.ITCS.2021.88},
  annote =	{Keywords: Online Bipartite Matching, Primal-Dual Analysis, Multi-stage Allocation, Batching}
}
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 About DROPS Imprint Privacy Contact