71 Search Results for "Zhang, Guochuan"

Volume

LIPIcs, Volume 149

30th International Symposium on Algorithms and Computation (ISAAC 2019)

ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China

Editors: Pinyan Lu and Guochuan Zhang

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.39
Approximation Algorithms for Interdiction Problem with Packing Constraints

Authors: Lin Chen, Xiaoyu Wu, and Guochuan Zhang

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

Abstract
We study a bilevel optimization problem which is a zero-sum Stackelberg game. In this problem, there are two players, a leader and a follower, who pick items from a common set. Both the leader and the follower have their own (multi-dimensional) budgets, respectively. Each item is associated with a profit, which is the same to the leader and the follower, and will consume the leader’s (follower’s) budget if it is selected by the leader (follower). The leader and the follower will select items in a sequential way: First, the leader selects items within the leader’s budget. Then the follower selects items from the remaining items within the follower’s budget. The goal of the leader is to minimize the maximum profit that the follower can obtain. Let s_A and s_B be the dimension of the leader’s and follower’s budget, respectively. A special case of our problem is the bilevel knapsack problem studied by Caprara et al. [SIAM Journal on Optimization, 2014], where s_A = s_B = 1. We consider the general problem and obtain an (s_B+ε)-approximation algorithm when s_A and s_B are both constant. In particular, if s_B = 1, our algorithm implies a PTAS for the bilevel knapsack problem, which is the first 𝒪(1)-approximation algorithm. We also complement our result by showing that there does not exist any (4/3-ε)-approximation algorithm even if s_A = 1 and s_B = 2. We also consider a variant of our problem with resource augmentation when s_A and s_B are both part of the input. We obtain an 𝒪(1)-approximation algorithm with 𝒪(1)-resource augmentation, that is, we give an algorithm that returns a solution which exceeds the given leader’s budget by 𝒪(1) times, and the objective value achieved by the solution is 𝒪(1) times the optimal objective value that respects the leader’s budget.
Cite as

Lin Chen, Xiaoyu Wu, and Guochuan Zhang. Approximation Algorithms for Interdiction Problem with Packing Constraints. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2022.39,
  author =	{Chen, Lin and Wu, Xiaoyu and Zhang, Guochuan},
  title =	{{Approximation Algorithms for Interdiction Problem with Packing Constraints}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{39:1--39:19},
  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.39},
  URN =		{urn:nbn:de:0030-drops-163806},
  doi =		{10.4230/LIPIcs.ICALP.2022.39},
  annote =	{Keywords: Bilevel Integer Programming, Interdiction Constraints, Knapsack}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2019
LIPIcs, Volume 149, ISAAC'19, Complete Volume

Authors: Pinyan Lu and Guochuan Zhang

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

Abstract
LIPIcs, Volume 149, ISAAC'19, Complete Volume
Cite as

30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{lu_et_al:LIPIcs.ISAAC.2019,
  title =	{{LIPIcs, Volume 149, ISAAC'19, Complete Volume}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  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},
  URN =		{urn:nbn:de:0030-drops-116417},
  doi =		{10.4230/LIPIcs.ISAAC.2019},
  annote =	{Keywords: Theory of computation; Models of computation; Computational complexity and cryptography; Randomness, geometry and discrete structures; Theory and algorithms for application domains; Design and analysis of algorithms}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2019.0
Front Matter, Table of Contents, Preface, Symposium Organization

Authors: Pinyan Lu and Guochuan Zhang

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

Abstract
Front Matter, Table of Contents, Preface, Symposium Organization
Cite as

30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.ISAAC.2019.0,
  author =	{Lu, Pinyan and Zhang, Guochuan},
  title =	{{Front Matter, Table of Contents, Preface, Symposium Organization}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{0:i--0:xvi},
  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.0},
  URN =		{urn:nbn:de:0030-drops-114967},
  doi =		{10.4230/LIPIcs.ISAAC.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Symposium Organization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.1
Graph Searches and Their End Vertices

Authors: Yixin Cao, Zhifeng Wang, Guozhen Rong, and Jianxin Wang

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

Abstract
Graph search, the process of visiting vertices in a graph in a specific order, has demonstrated magical powers in many important algorithms. But a systematic study was only initiated by Corneil et al. a decade ago, and only by then we started to realize how little we understand it. Even the apparently naïve question "which vertex can be the last visited by a graph search algorithm," known as the end vertex problem, turns out to be quite elusive. We give a full picture of all maximum cardinality searches on chordal graphs, which implies a polynomial-time algorithm for the end vertex problem of maximum cardinality search. It is complemented by a proof of NP-completeness of the same problem on weakly chordal graphs. We also show linear-time algorithms for deciding end vertices of breadth-first searches on interval graphs, and end vertices of lexicographic depth-first searches on chordal graphs. Finally, we present 2^n * n^O(1)-time algorithms for deciding the end vertices of breadth-first searches, depth-first searches, and maximum cardinality searches on general graphs.
Cite as

Yixin Cao, Zhifeng Wang, Guozhen Rong, and Jianxin Wang. Graph Searches and Their End Vertices. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ISAAC.2019.1,
  author =	{Cao, Yixin and Wang, Zhifeng and Rong, Guozhen and Wang, Jianxin},
  title =	{{Graph Searches and Their End Vertices}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{1:1--1:18},
  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.1},
  URN =		{urn:nbn:de:0030-drops-114973},
  doi =		{10.4230/LIPIcs.ISAAC.2019.1},
  annote =	{Keywords: maximum cardinality search, (lexicographic) breadth-first search, (lexicographic) depth-first search, chordal graph, weighted clique graph, end vertex}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.2
Lower Bound for Non-Adaptive Estimation of the Number of Defective Items

Authors: Nader H. Bshouty

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

Abstract
We prove that to estimate within a constant factor the number of defective items in a non-adaptive randomized group testing algorithm we need at least Omega~(log n) tests. This solves the open problem posed by Damaschke and Sheikh Muhammad in [Peter Damaschke and Azam Sheikh Muhammad, 2010; Peter Damaschke and Azam Sheikh Muhammad, 2010].
Cite as

Nader H. Bshouty. Lower Bound for Non-Adaptive Estimation of the Number of Defective Items. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.ISAAC.2019.2,
  author =	{Bshouty, Nader H.},
  title =	{{Lower Bound for Non-Adaptive Estimation of the Number of Defective Items}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{2:1--2:9},
  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.2},
  URN =		{urn:nbn:de:0030-drops-114983},
  doi =		{10.4230/LIPIcs.ISAAC.2019.2},
  annote =	{Keywords: Group Testing, Estimation, Defective Items}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.3
A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions

Authors: Kazuya Haraguchi and Hiroshi Nagamochi

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

Abstract
We are given an instance (G,I,sigma) with a graph G=(V,E), a set I of items, and a function sigma:V -> 2^I. For a subset X of V, let G[X] denote the subgraph induced from G by X, and I_sigma(X) denote the common item set over X. A subset X of V such that G[X] is connected is called a connector if, for any vertex v in V\X, G[X cup {v}] is not connected or I_sigma(X cup {v}) is a proper subset of I_sigma(X). In this paper, we present the first polynomial-delay algorithm for enumerating all connectors. For this, we first extend the problem of enumerating connectors to a general setting so that the connectivity condition on X in G can be specified in a more flexible way. We next design a new algorithm for enumerating all solutions in the general setting, which leads to a polynomial-delay algorithm for enumerating all connectors for several connectivity conditions on X in G, such as the biconnectivity of G[X] or the k-edge-connectivity among vertices in X in G.
Cite as

Kazuya Haraguchi and Hiroshi Nagamochi. A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haraguchi_et_al:LIPIcs.ISAAC.2019.3,
  author =	{Haraguchi, Kazuya and Nagamochi, Hiroshi},
  title =	{{A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{3:1--3:15},
  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.3},
  URN =		{urn:nbn:de:0030-drops-114990},
  doi =		{10.4230/LIPIcs.ISAAC.2019.3},
  annote =	{Keywords: Graph with itemsets, Enumeration, Polynomial-delay algorithms, Connectors}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.4
Top Tree Compression of Tries

Authors: Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann

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

Abstract
We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supports efficient prefix search queries. Namely, we show how to preprocess a set of strings of total length n over an alphabet of size sigma into a compressed data structure of worst-case optimal size O(n/log_sigma n) that given a pattern string P of length m determines if P is a prefix of one of the strings in time O(min(m log sigma,m + log n)). We show that this query time is in fact optimal regardless of the size of the data structure. Existing solutions either use Omega(n) space or rely on word RAM techniques, such as tabulation, hashing, address arithmetic, or word-level parallelism, and hence do not work on a pointer machine. Our result is the first solution on a pointer machine that achieves worst-case o(n) space. Along the way, we develop several interesting data structures that work on a pointer machine and are of independent interest. These include an optimal data structures for random access to a grammar-compressed string and an optimal data structure for a variant of the level ancestor problem.
Cite as

Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann. Top Tree Compression of Tries. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bille_et_al:LIPIcs.ISAAC.2019.4,
  author =	{Bille, Philip and Gawrychowski, Pawe{\l} and G{\o}rtz, Inge Li and Landau, Gad M. and Weimann, Oren},
  title =	{{Top Tree Compression of Tries}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{4:1--4:18},
  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.4},
  URN =		{urn:nbn:de:0030-drops-115000},
  doi =		{10.4230/LIPIcs.ISAAC.2019.4},
  annote =	{Keywords: pattern matching, tree compression, top trees, pointer machine}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.5
Two Phase Transitions in Two-Way Bootstrap Percolation

Authors: Ahad N. Zehmakan

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

Abstract
Consider a graph G and an initial random configuration, where each node is black with probability p and white otherwise, independently. In discrete-time rounds, each node becomes black if it has at least r black neighbors and white otherwise. We prove that this basic process exhibits a threshold behavior with two phase transitions when the underlying graph is a d-dimensional torus and identify the threshold values.
Cite as

Ahad N. Zehmakan. Two Phase Transitions in Two-Way Bootstrap Percolation. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{zehmakan:LIPIcs.ISAAC.2019.5,
  author =	{Zehmakan, Ahad N.},
  title =	{{Two Phase Transitions in Two-Way Bootstrap Percolation}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{5:1--5:21},
  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.5},
  URN =		{urn:nbn:de:0030-drops-115017},
  doi =		{10.4230/LIPIcs.ISAAC.2019.5},
  annote =	{Keywords: bootstrap percolation, cellular automata, phase transition, d-dimensional torus, r-threshold model, biased majority}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.6
Sliding Window Property Testing for Regular Languages

Authors: Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya

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

Abstract
We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window n and a stream of symbols. At each time instant, we must decide whether the suffix of length n of the current stream ("the active window") belongs to a given regular language. Recent works [Moses Ganardi et al., 2018; Moses Ganardi et al., 2016] showed that the space complexity of an optimal deterministic sliding window algorithm for this problem is either constant, logarithmic or linear in the window size n and provided natural language theoretic characterizations of the space complexity classes. Subsequently, [Moses Ganardi et al., 2018] extended this result to randomized algorithms to show that any such algorithm admits either constant, double logarithmic, logarithmic or linear space complexity. In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We show that for every regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.
Cite as

Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding Window Property Testing for Regular Languages. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.ISAAC.2019.6,
  author =	{Ganardi, Moses and Hucke, Danny and Lohrey, Markus and Starikovskaya, Tatiana},
  title =	{{Sliding Window Property Testing for Regular Languages}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{6:1--6:13},
  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.6},
  URN =		{urn:nbn:de:0030-drops-115023},
  doi =		{10.4230/LIPIcs.ISAAC.2019.6},
  annote =	{Keywords: Streaming algorithms, approximation algorithms, regular languages}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.7
On the Hardness of Set Disjointness and Set Intersection with Bounded Universe

Authors: Isaac Goldstein, Moshe Lewenstein, and Ely Porat

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

Abstract
In the SetDisjointness problem, a collection of m sets S_1,S_2,...,S_m from some universe U is preprocessed in order to answer queries on the emptiness of the intersection of some two query sets from the collection. In the SetIntersection variant, all the elements in the intersection of the query sets are required to be reported. These are two fundamental problems that were considered in several papers from both the upper bound and lower bound perspective. Several conditional lower bounds for these problems were proven for the tradeoff between preprocessing and query time or the tradeoff between space and query time. Moreover, there are several unconditional hardness results for these problems in some specific computational models. The fundamental nature of the SetDisjointness and SetIntersection problems makes them useful for proving the conditional hardness of other problems from various areas. However, the universe of the elements in the sets may be very large, which may cause the reduction to some other problems to be inefficient and therefore it is not useful for proving their conditional hardness. In this paper, we prove the conditional hardness of SetDisjointness and SetIntersection with bounded universe. This conditional hardness is shown for both the interplay between preprocessing and query time and the interplay between space and query time. Moreover, we present several applications of these new conditional lower bounds. These applications demonstrates the strength of our new conditional lower bounds as they exploit the limited universe size. We believe that this new framework of conditional lower bounds with bounded universe can be useful for further significant applications.
Cite as

Isaac Goldstein, Moshe Lewenstein, and Ely Porat. On the Hardness of Set Disjointness and Set Intersection with Bounded Universe. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goldstein_et_al:LIPIcs.ISAAC.2019.7,
  author =	{Goldstein, Isaac and Lewenstein, Moshe and Porat, Ely},
  title =	{{On the Hardness of Set Disjointness and Set Intersection with Bounded Universe}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{7:1--7:22},
  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.7},
  URN =		{urn:nbn:de:0030-drops-115036},
  doi =		{10.4230/LIPIcs.ISAAC.2019.7},
  annote =	{Keywords: set disjointness, set intersection, 3SUM, space-time tradeoff, conditional lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.8
Gathering and Election by Mobile Robots in a Continuous Cycle

Authors: Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita

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

Abstract
Consider a set of n mobile computational entities, called robots, located and operating on a continuous cycle C (e.g., the perimeter of a closed region of R^2) of arbitrary length l. The robots are identical, can only see their current location, have no location awareness, and cannot communicate at a distance. In this weak setting, we study the classical problems of gathering (GATHER), requiring all robots to meet at a same location; and election (ELECT), requiring all robots to agree on a single one as the "leader". We investigate how to solve the problems depending on the amount of knowledge (exact, upper bound, none) the robots have about their number n and about the length of the cycle l. Cost of the algorithms is analyzed with respect to time and number of random bits. We establish a variety of new results specific to the continuous cycle - a geometric domain never explored before for GATHER and ELECT in a mobile robot setting; compare Monte Carlo and Las Vegas algorithms; and obtain several optimal bounds.
Cite as

Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita. Gathering and Election by Mobile Robots in a Continuous Cycle. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{flocchini_et_al:LIPIcs.ISAAC.2019.8,
  author =	{Flocchini, Paola and Killick, Ryan and Kranakis, Evangelos and Santoro, Nicola and Yamashita, Masafumi},
  title =	{{Gathering and Election by Mobile Robots in a Continuous Cycle}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-115044},
  doi =		{10.4230/LIPIcs.ISAAC.2019.8},
  annote =	{Keywords: Cycle, Election, Gathering, Las Vegas, Monte Carlo, Randomized Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.9
Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists

Authors: Koki Hamada, Shuichi Miyazaki, and Hiroki Yanagisawa

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

Abstract
In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property that it is strategy-proof to the men’s side, i.e., no man can obtain a better outcome by falsifying a preference list. We call such a mechanism a man-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proof mechanism. (Of course, if we flip the roles of men and women, we can see that the woman-oriented Gale-Shapley algorithm (WGS) is a woman-strategy-proof but not a man-strategy-proof mechanism.) Roth has shown that there is no stable mechanism that is simultaneously man-strategy-proof and woman-strategy-proof, which is known as Roth’s impossibility theorem. In this paper, we extend these results to the stable marriage problem with ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth’s impossibility theorem takes over to SMTI. Therefore, we focus on the one-sided-strategy-proofness. In SMTI, one instance can have stable matchings of different sizes, and it is natural to consider the problem of finding a largest stable matching, known as MAX SMTI. Thus we incorporate the notion of approximation ratios used in the theory of approximation algorithms. We say that a stable-mechanism is a c-approximate-stable mechanism if it always returns a stable matching of size at least 1/c of a largest one. We also consider a restricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men’s lists can contain ties (and women’s lists must be strictly ordered). Our results are summarized as follows: (i) MAX SMTI admits both a man-strategy-proof 2-approximate-stable mechanism and a woman-strategy-proof 2-approximate-stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof 2-approximate-stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof 1.5-approximate-stable mechanism. All these results are tight in terms of approximation ratios. Also, all these results apply for strategy-proofness against coalitions.
Cite as

Koki Hamada, Shuichi Miyazaki, and Hiroki Yanagisawa. Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hamada_et_al:LIPIcs.ISAAC.2019.9,
  author =	{Hamada, Koki and Miyazaki, Shuichi and Yanagisawa, Hiroki},
  title =	{{Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{9:1--9:14},
  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.9},
  URN =		{urn:nbn:de:0030-drops-115059},
  doi =		{10.4230/LIPIcs.ISAAC.2019.9},
  annote =	{Keywords: Stable marriage problem, strategy-proofness, approximation algorithm, ties, incomplete lists}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.10
Online Multidimensional Packing Problems in the Random-Order Model

Authors: David Naori and Danny Raz

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

Abstract
We study online multidimensional variants of the generalized assignment problem which are used to model prominent real-world applications, such as the assignment of virtual machines with multiple resource requirements to physical infrastructure in cloud computing. These problems can be seen as an extension of the well known secretary problem and thus the standard online worst-case model cannot provide any performance guarantee. The prevailing model in this case is the random-order model, which provides a useful realistic and robust alternative. Using this model, we study the d-dimensional generalized assignment problem, where we introduce a novel technique that achieves an O(d)-competitive algorithms and prove a matching lower bound of Omega(d). Furthermore, our algorithm improves upon the best-known competitive-ratio for the online (one-dimensional) generalized assignment problem and the online knapsack problem.
Cite as

David Naori and Danny Raz. Online Multidimensional Packing Problems in the Random-Order Model. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{naori_et_al:LIPIcs.ISAAC.2019.10,
  author =	{Naori, David and Raz, Danny},
  title =	{{Online Multidimensional Packing Problems in the Random-Order Model}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{10:1--10:15},
  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.10},
  URN =		{urn:nbn:de:0030-drops-115067},
  doi =		{10.4230/LIPIcs.ISAAC.2019.10},
  annote =	{Keywords: Random Order, Generalized Assignment Problem, Knapsack Problem, Multidimensional Packing, Secretary Problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.11
Approximate Euclidean Shortest Paths in Polygonal Domains

Authors: R. Inkulu and Sanjiv Kapoor

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

Abstract
Given a set P of h pairwise disjoint simple polygonal obstacles in R^2 defined with n vertices, we compute a sketch Omega of P whose size is independent of n, depending only on h and the input parameter epsilon. We utilize Omega to compute a (1+epsilon)-approximate geodesic shortest path between the two given points in O(n + h((lg n) + (lg h)^(1+delta) + (1/epsilon) lg(h/epsilon)))) time. Here, epsilon is a user parameter, and delta is a small positive constant (resulting from the time for triangulating the free space of P using the algorithm in [Bar-Yehuda and Chazelle, 1994]). Moreover, we devise a (2+epsilon)-approximation algorithm to answer two-point Euclidean distance queries for the case of convex polygonal obstacles.
Cite as

R. Inkulu and Sanjiv Kapoor. Approximate Euclidean Shortest Paths in Polygonal Domains. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{inkulu_et_al:LIPIcs.ISAAC.2019.11,
  author =	{Inkulu, R. and Kapoor, Sanjiv},
  title =	{{Approximate Euclidean Shortest Paths in Polygonal Domains}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-115075},
  doi =		{10.4230/LIPIcs.ISAAC.2019.11},
  annote =	{Keywords: Computational Geometry, Geometric Shortest Paths, Approximation Algorithms}
}
  • Refine by Author
  • 6 Zhang, Guochuan
  • 4 Chen, Lin
  • 3 Wang, Jianxin
  • 2 Bar-Noy, Amotz
  • 2 Buchin, Maike
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 approximation algorithms
  • 3 data structures
  • 2 Approximation
  • 2 Approximation Algorithms
  • 2 Fréchet distance
  • Show More...

  • Refine by Type
  • 70 document
  • 1 volume

  • Refine by Publication Year
  • 67 2019
  • 2 2016
  • 1 2017
  • 1 2022

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