12 Search Results for "Zhang, Yuhao"


Document
APPROX
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
APPROX
On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting

Authors: Mayank Goswami and Riko Jacob

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


Abstract
We generalize the classical nuts and bolts problem to a setting where the input is a collection of n nuts and m bolts, and there is no promise of any matching pairs. It is not allowed to compare a nut directly with a nut or a bolt directly with a bolt, and the goal is to perform the fewest nut-bolt comparisons to discover the partial order between the nuts and bolts. We term this problem bipartite sorting. We show that instances of bipartite sorting of the same size exhibit a wide range of complexity, and propose to perform a fine-grained analysis for this problem. We rule out straightforward notions of instance-optimality as being too stringent, and adopt a neighborhood-based definition. Our definition may be of independent interest as a unifying lens for instance-optimal algorithms for other static problems existing in literature. This includes problems like sorting (Estivill-Castro and Woods, ACM Comput. Surv. 1992), convex hull (Afshani, Barbay and Chan, JACM 2017), adaptive joins (Demaine, López-Ortiz and Munro, SODA 2000), and the recent concept of universal optimality for graphs (Haeupler, Hladík, Rozhoň, Tarjan and Tětek, 2023). As our main result on bipartite sorting, we give a randomized algorithm that is within a factor of O(log³(n+m)) of being instance-optimal w.h.p., with respect to the neighborhood-based definition. As our second contribution, we generalize bipartite sorting to DAG sorting, when the underlying DAG is not necessarily bipartite. As an unexpected consequence of a simple algorithm for DAG sorting, we rule out a potential lower bound on the widely-studied problem of sorting with priced information, posed by (Charikar, Fagin, Guruswami, Kleinberg, Raghavan and Sahai, STOC 2000). In this problem, comparing keys i and j has a known cost c_{ij} ∈ ℝ^+ ∪ {∞}, and the goal is to sort the keys in an instance-optimal way, by keeping the total cost of an algorithm as close as possible to ∑_{i=1}^{n-1} c_{x(i)x(i+1)}. Here x(1) < ⋯ < x(n) is the sorted order. While several special cases of cost functions have received a lot of attention in the community, no progress on the general version with arbitrary costs has been reported so far. One reason for this lack of progress seems to be a widely-cited Ω(n) lower bound on the competitive ratio for finding the maximum. This Ω(n) lower bound by (Gupta and Kumar, FOCS 2000) uses costs in {0,1,n, ∞}, and although not extended to sorting, this barrier seems to have stalled any progress on the general cost case. We rule out such a potential lower bound by showing the existence of an algorithm with a Õ(n^{3/4}) competitive ratio for the {0,1,n,∞} cost version. This generalizes the setting of generalized sorting proposed by (Huang, Kannan and Khanna, FOCS 2011), where the costs are either 1 or infinity, and the cost of the cheapest proof is always n-1.

Cite as

Mayank Goswami and Riko Jacob. On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{goswami_et_al:LIPIcs.APPROX/RANDOM.2024.23,
  author =	{Goswami, Mayank and Jacob, Riko},
  title =	{{On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-210168},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.23},
  annote =	{Keywords: Sorting, Priced Information, Instance Optimality, Nuts and Bolts}
}
Document
Generalizing Shape Analysis with Gradual Types

Authors: Zeina Migeed, James Reed, Jason Ansel, and Jens Palsberg

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)


Abstract
Tensors are multi-dimensional data structures that can represent the data processed by machine learning tasks. Tensor programs tend to be short and readable, and they can leverage libraries and frameworks such as TensorFlow and PyTorch, as well as modern hardware such as GPUs and TPUs. However, tensor programs also tend to obscure shape information, which can cause shape errors that are difficult to find. Such shape errors can be avoided by a combination of shape annotations and shape analysis, but such annotations are burdensome to come up with manually. In this paper, we use gradual typing to reduce the barrier of entry. Gradual typing offers a way to incrementally introduce type annotations into programs. From there, we focus on tool support for type migration, which is a concept that closely models code-annotation tasks and allows us to do shape reasoning and utilize it for different purposes. We develop a comprehensive gradual typing theory to reason about tensor shapes. We then ask three fundamental questions about a gradually typed tensor program. (1) Does the program have a static migration? (2) Given a program and some arithmetic constraints on shapes, can we migrate the program according to the constraints? (3) Can we eliminate branches that depend on shapes? We develop novel tools to address the three problems. For the third problem, there are currently two PyTorch tools that aim to eliminate branches. They do so by eliminating them for just a single input. Our tool is the first to eliminate branches for an infinite class of inputs, using static shape information. Our tools help prevent bugs, alleviate the burden on the programmer of annotating the program, and improves the process of program transformation.

Cite as

Zeina Migeed, James Reed, Jason Ansel, and Jens Palsberg. Generalizing Shape Analysis with Gradual Types. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 29:1-29:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{migeed_et_al:LIPIcs.ECOOP.2024.29,
  author =	{Migeed, Zeina and Reed, James and Ansel, Jason and Palsberg, Jens},
  title =	{{Generalizing Shape Analysis with Gradual Types}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{29:1--29:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.29},
  URN =		{urn:nbn:de:0030-drops-208786},
  doi =		{10.4230/LIPIcs.ECOOP.2024.29},
  annote =	{Keywords: Tensor Shapes, Gradual Types, Migration}
}
Document
Track A: Algorithms, Complexity and Games
Algorithms for the Generalized Poset Sorting Problem

Authors: Shaofeng H.-C. Jiang, Wenqian Wang, Yubo Zhang, and Yuhao Zhang

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


Abstract
We consider a generalized poset sorting problem (GPS), in which we are given a query graph G = (V, E) and an unknown poset 𝒫(V, ≺) that is defined on the same vertex set V, and the goal is to make as few queries as possible to edges in G in order to fully recover 𝒫, where each query (u, v) returns the relation between u, v, i.e., u ≺ v, v ≺ u or u ̸ ∼ v. This generalizes both the poset sorting problem [Faigle et al., SICOMP 88] and the generalized sorting problem [Huang et al., FOCS 11]. We give algorithms with Õ(n poly(k)) query complexity when G is a complete bipartite graph or G is stochastic under the Erdős-Rényi model, where k is the width of the poset, and these generalize [Daskalakis et al., SICOMP 11] which only studies complete graph G. Both results are based on a unified framework that reduces the poset sorting to partitioning the vertices with respect to a given pivot element, which may be of independent interest. Moreover, we also propose novel algorithms to implement this partition oracle. Notably, we suggest a randomized BFS with vertex skipping for the stochastic G, and it yields a nearly-tight bound even for the special case of generalized sorting (for stochastic G) which is comparable to the main result of a recent work [Kuszmaul et al., FOCS 21] but is conceptually different and simplified. Our study of GPS also leads to a new Õ(n^{1 - 1 / (2W)}) competitive ratio for the so-called weighted generalized sorting problem where W is the number of distinct weights in the query graph. This problem was considered as an open question in [Charikar et al., JCSS 02], and our result makes important progress as it yields the first nontrivial sublinear ratio for general weighted query graphs (for any bounded W). We obtain this via an Õ(nk + n^{1.5}) query complexity algorithm for the case where every edge in G is guaranteed to be comparable in the poset, which generalizes a Õ(n^{1.5}) bound for generalized sorting [Huang et al., FOCS 11].

Cite as

Shaofeng H.-C. Jiang, Wenqian Wang, Yubo Zhang, and Yuhao Zhang. Algorithms for the Generalized Poset Sorting Problem. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 92:1-92:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ICALP.2024.92,
  author =	{Jiang, Shaofeng H.-C. and Wang, Wenqian and Zhang, Yubo and Zhang, Yuhao},
  title =	{{Algorithms for the Generalized Poset Sorting Problem}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{92:1--92:15},
  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.92},
  URN =		{urn:nbn:de:0030-drops-202359},
  doi =		{10.4230/LIPIcs.ICALP.2024.92},
  annote =	{Keywords: sorting, poset sorting, generalized sorting}
}
Document
Short Paper
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
On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching

Authors: Jingxun Liang, Zhihao Gavin Tang, Yixuan Even Xu, Yuhao Zhang, and Renfei Zhou

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
Ranking and Balance are arguably the two most important algorithms in the online matching literature. They achieve the same optimal competitive ratio of 1-1/e for the integral version and fractional version of online bipartite matching by Karp, Vazirani, and Vazirani (STOC 1990) respectively. The two algorithms have been generalized to weighted online bipartite matching problems, including vertex-weighted online bipartite matching and AdWords, by utilizing a perturbation function. The canonical choice of the perturbation function is f(x) = 1-e^{x-1} as it leads to the optimal competitive ratio of 1-1/e in both settings. We advance the understanding of the weighted generalizations of Ranking and Balance in this paper, with a focus on studying the effect of different perturbation functions. First, we prove that the canonical perturbation function is the unique optimal perturbation function for vertex-weighted online bipartite matching. In stark contrast, all perturbation functions achieve the optimal competitive ratio of 1-1/e in the unweighted setting. Second, we prove that the generalization of Ranking to AdWords with unknown budgets using the canonical perturbation function is at most 0.624 competitive, refuting a conjecture of Vazirani (2021). More generally, as an application of the first result, we prove that no perturbation function leads to the prominent competitive ratio of 1-1/e by establishing an upper bound of 1-1/e-0.0003. Finally, we propose the online budget-additive welfare maximization problem that is intermediate between AdWords and AdWords with unknown budgets, and we design an optimal 1-1/e competitive algorithm by generalizing Balance.

Cite as

Jingxun Liang, Zhihao Gavin Tang, Yixuan Even Xu, Yuhao Zhang, and Renfei Zhou. On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 80:1-80:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{liang_et_al:LIPIcs.ESA.2023.80,
  author =	{Liang, Jingxun and Tang, Zhihao Gavin and Xu, Yixuan Even and Zhang, Yuhao and Zhou, Renfei},
  title =	{{On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{80:1--80:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.80},
  URN =		{urn:nbn:de:0030-drops-187334},
  doi =		{10.4230/LIPIcs.ESA.2023.80},
  annote =	{Keywords: Online Matching, AdWords, Ranking, Water-Filling}
}
Document
Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs

Authors: Enze Sun, Zonghan Yang, and Yuhao Zhang

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
We consider the Online Rent Minimization problem, where online jobs with release times, deadlines, and processing times must be scheduled on machines that can be rented for a fixed length period of T. The objective is to minimize the number of machine rents. This problem generalizes the Online Machine Minimization problem where machines can be rented for an infinite period, and both problems have an asymptotically optimal competitive ratio of O(log(p_max/p_min)) for general processing times, where p_max and p_min are the maximum and minimum processing times respectively. However, for small values of p_max/p_min, a better competitive ratio can be achieved by assuming unit-size jobs. Under this assumption, Devanur et al. (2014) gave an optimal e-competitive algorithm for Online Machine Minimization, and Chen and Zhang (2022) gave a (3e+7) ≈ 15.16-competitive algorithm for Online Rent Minimization. In this paper, we significantly improve the competitive ratio of the Online Rent Minimization problem under unit size to 6, by using a clean oracle-based online algorithm framework.

Cite as

Enze Sun, Zonghan Yang, and Yuhao Zhang. Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 97:1-97:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ESA.2023.97,
  author =	{Sun, Enze and Yang, Zonghan and Zhang, Yuhao},
  title =	{{Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{97:1--97:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.97},
  URN =		{urn:nbn:de:0030-drops-187500},
  doi =		{10.4230/LIPIcs.ESA.2023.97},
  annote =	{Keywords: Online Algorithm, Scheduling, Machine Minimization, Rent Minimization}
}
Document
Minimizing the Maximum Flow Time in the Online Food Delivery Problem

Authors: Xiangyu Guo, Kelin Luo, Shi Li, and Yuhao Zhang

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where k vehicles of capacity c are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order. We show that the problem is hard in both offline and online settings even when k = 1 and c = ∞: There is a hardness of approximation of Ω(n) for the offline problem, and a lower bound of Ω(n) on the competitive ratio of any online algorithm, where n is number of points in the metric. We circumvent the strong negative results in two directions. Our main result is an O(1)-competitive online algorithm for the uncapacitated (i.e, c = ∞) food delivery problem on tree metrics; we also have negative result showing that the condition c = ∞ is needed. Then we explore the speed-augmentation model where our online algorithm is allowed to use vehicles with faster speed. We show that a moderate speeding factor leads to a constant competitive ratio, and we prove a tight trade-off between the speeding factor and the competitive ratio.

Cite as

Xiangyu Guo, Kelin Luo, Shi Li, and Yuhao Zhang. Minimizing the Maximum Flow Time in the Online Food Delivery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.ISAAC.2022.33,
  author =	{Guo, Xiangyu and Luo, Kelin and Li, Shi and Zhang, Yuhao},
  title =	{{Minimizing the Maximum Flow Time in the Online Food Delivery Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.33},
  URN =		{urn:nbn:de:0030-drops-173181},
  doi =		{10.4230/LIPIcs.ISAAC.2022.33},
  annote =	{Keywords: Online algorithm, Capacitated Vehicle Routing, Flow Time Optimization}
}
Document
Track A: Algorithms, Complexity and Games
Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity

Authors: Chao Liao, Qingyun Chen, Bundit Laekhanukit, and Yuhao Zhang

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
In the k-outconnected directed Steiner tree problem (k-DST), we are given an n-vertex directed graph G = (V,E) with edge costs, a connectivity requirement k, a root r ∈ V and a set of terminals T ⊆ V. The goal is to find a minimum-cost subgraph H ⊆ G that has k edge-disjoint paths from the root vertex r to every terminal t ∈ T. The problem is NP-hard, and inapproximability results are known in several parameters, e.g., hardness in terms of n: log^{2-ε}n-hardness for k = 1 [Halperin and Krauthgamer, STOC'03], 2^{log^{1-ε}n}-hardness for general case [Cheriyan, Laekhanukit, Naves and Vetta, SODA'12], hardness in terms of k [Cheriyan et al., SODA'12; Laekhanukit, SODA'14; Manurangsi, IPL'19] and hardness in terms of |T| [Laekhanukit, SODA'14]. In this paper, we show the approximation hardness of k-DST for various parameters. - Ω(|T|/log |T|)-approximation hardness, which holds under the standard complexity assumption NP≠ ZPP. The inapproximability ratio is tightened to Ω(|T|) under the Strongish Planted Clique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021]. The latter hardness result matches the approximation ratio of |T| obtained by a trivial approximation algorithm, thus closing the long-standing open problem. - Ω(2^{k/2} / k)-approximation hardness for the general case of k-DST under the assumption NP≠ZPP. This is the first hardness result known for survivable network design problems with an inapproximability ratio exponential in k. - Ω((k/L)^{L/4})-approximation hardness for k-DST on L-layered graphs for L ≤ O(log n). This almost matches the approximation ratio of O(k^{L-1}⋅ L ⋅ log |T|) achieved in O(n^L)-time due to Laekhanukit [ICALP'16]. We further extend our hardness results in terms of |T| to the undirected cases of k-DST, namely the single-source k-vertex-connected Steiner tree and the k-edge-connected group Steiner tree problems. Thus, we obtain Ω(|T|/log |T|) and Ω(|T|) approximation hardness for both problems under the assumption NP≠ ZPP and the Strongish Planted Clique Hypothesis, respectively. This again matches the upper bound obtained by trivial algorithms.

Cite as

Chao Liao, Qingyun Chen, Bundit Laekhanukit, and Yuhao Zhang. Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{liao_et_al:LIPIcs.ICALP.2022.89,
  author =	{Liao, Chao and Chen, Qingyun and Laekhanukit, Bundit and Zhang, Yuhao},
  title =	{{Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{89:1--89:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.89},
  URN =		{urn:nbn:de:0030-drops-164309},
  doi =		{10.4230/LIPIcs.ICALP.2022.89},
  annote =	{Keywords: Directed Steiner Tree, Hardness of Approximation, Fault-Tolerant and Survivable Network Design}
}
Document
APPROX
Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

Authors: Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, and Yuhao Zhang

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


Abstract
In the k-Connected Directed Steiner Tree problem (k-DST), we are given a directed graph G = (V,E) with edge (or vertex) costs, a root vertex r, a set of q terminals T, and a connectivity requirement k > 0; the goal is to find a minimum-cost subgraph H of G such that H has k edge-disjoint paths from the root r to each terminal in T. The k-DST problem is a natural generalization of the classical Directed Steiner Tree problem (DST) in the fault-tolerant setting in which the solution subgraph is required to have an r,t-path, for every terminal t, even after removing k-1 vertices or edges. Despite being a classical problem, there are not many positive results on the problem, especially for the case k ≥ 3. In this paper, we present an O(log k log q)-approximation algorithm for k-DST when an input graph is quasi-bipartite, i.e., when there is no edge joining two non-terminal vertices. To the best of our knowledge, our algorithm is the only known non-trivial approximation algorithm for k-DST, for k ≥ 3, that runs in polynomial-time Our algorithm is tight for every constant k, due to the hardness result inherited from the Set Cover problem.

Cite as

Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, and Yuhao Zhang. Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 63:1-63:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.APPROX/RANDOM.2020.63,
  author =	{Chan, Chun-Hsiang and Laekhanukit, Bundit and Wei, Hao-Ting and Zhang, Yuhao},
  title =	{{Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{63:1--63:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.63},
  URN =		{urn:nbn:de:0030-drops-126667},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.63},
  annote =	{Keywords: Approximation Algorithms, Network Design, Directed Graphs}
}
Document
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}
}
Document
Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

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

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1/e barrier even in the vertex-weighted case. We build on the randomized primal-dual framework by Devanur et al. (SODA 2013) and design a two dimensional gain sharing function, which depends not only on the rank of the offline vertex, but also on the arrival time of the online vertex. To our knowledge, this is the first competitive ratio strictly larger than 1-1/e for an online bipartite matching problem achieved under the randomized primal-dual framework. Our algorithm has a natural interpretation that offline vertices offer a larger portion of their weights to the online vertices as time goes by, and each online vertex matches the neighbor with the highest offer at its arrival.

Cite as

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2018.79,
  author =	{Huang, Zhiyi and Tang, Zhihao Gavin and Wu, Xiaowei and Zhang, Yuhao},
  title =	{{Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.79},
  URN =		{urn:nbn:de:0030-drops-90830},
  doi =		{10.4230/LIPIcs.ICALP.2018.79},
  annote =	{Keywords: Vertex Weighted, Online Bipartite Matching, Randomized Primal-Dual}
}
  • Refine by Author
  • 8 Zhang, Yuhao
  • 3 Tang, Zhihao Gavin
  • 2 Huang, Zhiyi
  • 2 Laekhanukit, Bundit
  • 2 Wu, Xiaowei
  • Show More...

  • Refine by Classification
  • 7 Theory of computation → Online algorithms
  • 3 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Sorting and searching
  • 1 Human-centered computing → Human computer interaction (HCI)
  • 1 Mathematics of computing → Approximation algorithms
  • Show More...

  • Refine by Keyword
  • 1 AdWords
  • 1 Approximation Algorithms
  • 1 Capacitated Vehicle Routing
  • 1 Cartography
  • 1 DALL-E
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 4 2024
  • 3 2023
  • 2 2018
  • 2 2022
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail