liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Polishchuk, Valentin
Publications (10 of 19) Show all publications
Bulusu, V., Polishchuk, V., Sengupta, R. & Sedov, L. (2017). Capacity estimation for low altitude airspace. In: 17th AIAA Aviation Technology, Integration, and Operations Conference: . Paper presented at 17th AIAA Aviation Technology, Integration, and Operations Conference, 5-9 June 2017, Denver, Colorado, USA (pp. 1-15). AIAA Association
Open this publication in new window or tab >>Capacity estimation for low altitude airspace
2017 (English)In: 17th AIAA Aviation Technology, Integration, and Operations Conference, AIAA Association , 2017, p. 1-15Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
AIAA Association, 2017
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-152720 (URN)10.2514/6.2017-4266 (DOI)978-1-62410-508-1 (ISBN)
Conference
17th AIAA Aviation Technology, Integration, and Operations Conference, 5-9 June 2017, Denver, Colorado, USA
Available from: 2018-11-16 Created: 2018-11-16 Last updated: 2018-11-22
Sedov, L., Polishchuk, V. & Josefsson, B. (2017). Towards Simplified Optimal Sector Splitting. In: Schaefer, Dirk (Ed.), Proceedings of the SESAR Innovation Days 2017: Selected scientific papers on air traffic management. Paper presented at SESAR Innovation Days 2017: Accelerating the pace of change in ATM, 28-30 November 2017, Belgrade, Serbia (pp. 84-95). SESAR joint undertaking
Open this publication in new window or tab >>Towards Simplified Optimal Sector Splitting
2017 (English)In: Proceedings of the SESAR Innovation Days 2017: Selected scientific papers on air traffic management / [ed] Schaefer, Dirk, SESAR joint undertaking , 2017, p. 84-95Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
SESAR joint undertaking, 2017
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-152721 (URN)10.2829/233548 (DOI)978-92-9216-095-1 (ISBN)978-92-9216-094-4 (ISBN)
Conference
SESAR Innovation Days 2017: Accelerating the pace of change in ATM, 28-30 November 2017, Belgrade, Serbia
Available from: 2018-11-16 Created: 2018-11-16 Last updated: 2018-12-10
Bae, S. W., Korman, M., Mitchell, J. S., Okamoto, Y., Polishchuk, V. & Wang, H. (2016). Computing the $ L_1 $ Geodesic Diameter and Center of a Polygonal Domain. Leibniz International Proceedings in Informatics, 47, 14:1-14:14
Open this publication in new window or tab >>Computing the $ L_1 $ Geodesic Diameter and Center of a Polygonal Domain
Show others...
2016 (English)In: Leibniz International Proceedings in Informatics, ISSN 1868-8969, E-ISSN 1868-8969, Vol. 47, p. 14:1-14:14Article in journal (Refereed) Published
Abstract [en]

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L1 geodesic diameter in O(n2+h4) time and the L1 geodesic center in O((n4+n2h4) (n)) time, where (·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n7.73) or O(n7(h+log n)) time, and compute the geodesic center in O(n12+) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L1 shortest paths in polygonal domains.

Place, publisher, year, edition, pages
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016
Keywords
geodesic diameter, geodesic center, shortest paths, polygonal domains, L1 metric
National Category
Computer Sciences Medical Image Processing
Identifiers
urn:nbn:se:liu:diva-128031 (URN)10.4230/LIPIcs.STACS.2016.14 (DOI)
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2018-01-10
Efrat, A., Fekete, S. P., Mitchell, J. S. B., Polishchuk, V. & Suomela, J. (2016). Improved Approximation Algorithms for Relay Placement. ACM Transactions on Algorithms, 12(2), 20
Open this publication in new window or tab >>Improved Approximation Algorithms for Relay Placement
Show others...
2016 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 12, no 2, p. 20-Article in journal (Refereed) Published
Abstract [en]

In the relay placement problem, the input is a set of sensors and a number r >= 1, the communication range of a relay. In the one-tier version of the problem, the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11-approximation algorithm for the one-tier version and a polynomial-time approximation scheme (PTAS) for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P not equal NP.

Place, publisher, year, edition, pages
ACM Press, 2016
Keywords
Wireless networks; relays; sensor networks; approximation algorithms; Steiner minimum spanning tree; polynomial-time approximation scheme (PTAS)
National Category
Civil Engineering
Identifiers
urn:nbn:se:liu:diva-127756 (URN)10.1145/2814938 (DOI)000373905400008 ()
Note

Funding Agencies|EU project FRONTS (FP7) [215270]; National Science Foundation [CCF-0431030, CCF-0528209, CCF-0729019, CCF-1018388, CCF-1540890, 0348000]; NASA Ames; Metron Aviation; Sandia National Labs; Academy of Finland [116547]; Helsinki Graduate School in Computer Science and Engineering (Hecse); Foundation of Nokia Corporation

Available from: 2016-05-12 Created: 2016-05-12 Last updated: 2017-11-30
Arkin, E. M., Efrat, A., Knauer, C., Mitchell, J. S., Polishchuk, V., Rote, G., . . . Talvitie, T. (2016). Shortest path to a segment and quickest visibility queries. In: LIPIcs-Leibniz International Proceedings in Informatics: . Paper presented at SoCG 15 (pp. 77-100). , 7
Open this publication in new window or tab >>Shortest path to a segment and quickest visibility queries
Show others...
2016 (English)In: LIPIcs-Leibniz International Proceedings in Informatics, 2016, Vol. 7, p. 77-100Conference paper, Published paper (Refereed)
Abstract [en]

We show how to preprocess a polygonal domain with a xed starting point s in order to answer eciently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortestpath- to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a di erent generalization of shortest-path-to-a-point queries, which may be of independent interest: to report eciently a shortest path from s to a query segment in the domain.

Series
Journal of Computational Geometry, ISSN 1920-180X
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-128034 (URN)
Conference
SoCG 15
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2018-01-10
Mitchell, J. S. B., Polishchuk, V., Sysikaski, M. & Wang, H. (2015). An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains. In: Automata, Languages, and Programming, Pt I: . Paper presented at 42nd International Colloquium on Automata, Languages and Programming (ICALP) (pp. 947-959). SPRINGER-VERLAG BERLIN, 9134
Open this publication in new window or tab >>An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
2015 (English)In: Automata, Languages, and Programming, Pt I, SPRINGER-VERLAG BERLIN , 2015, Vol. 9134, p. 947-959Conference paper, Published paper (Refereed)
Abstract [en]

We present a new algorithm for finding minimum-link rectilinear paths among h rectilinear obstacles with a total of n vertices in the plane. After the plane is triangulated, for any point s, our algorithm builds an O(n)-size data structure in O(n+h log h) time, such that given any query point t, we can compute a minimum-link rectilinear path from s to t in O(log n + k) time, where k is the number of edges of the path, and the query time is O(log n) if we only want to know the value k. The previously best algorithm solves the problem in O(n log n) time.

Place, publisher, year, edition, pages
SPRINGER-VERLAG BERLIN, 2015
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 9134
National Category
Civil Engineering
Identifiers
urn:nbn:se:liu:diva-123168 (URN)10.1007/978-3-662-47672-7_77 (DOI)000364317700077 ()978-3-662-47672-7 (ISBN)978-3-662-47671-0 (ISBN)
Conference
42nd International Colloquium on Automata, Languages and Programming (ICALP)
Available from: 2015-12-06 Created: 2015-12-04 Last updated: 2018-02-02
Golovin, D., Goyal, V., Polishchuk, V., Ravi, R. & Sysikaski, M. (2015). Improved approximations for two-stage min-cut and shortest path problems under uncertainty. Mathematical Programming, 149(1), 167-194
Open this publication in new window or tab >>Improved approximations for two-stage min-cut and shortest path problems under uncertainty
Show others...
2015 (English)In: Mathematical Programming, ISSN 0025-5610, Vol. 149, no 1, p. 167-194Article in journal (Refereed) Published
Abstract [en]

In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. (in How to pay, come what may: approximation algorithms for demand-robust covering problems. In: FOCS, pp 367–378, 2005), and give approximation algorithms with improved approximation factors. Specifically, we give a 2-approximation for the robust min-cut problem and a 4-approximation for the stochastic version. For the two-stage shortest path problem, we give a 3.39'>3.39 3.39 -approximation for the robust version and 6.78'>6.78 6.78 -approximation for the stochastic version. Our results significantly improve the previous best approximation factors for the problems. In particular, we provide the first constant-factor approximation for the stochastic min-cut problem. Our algorithms are based on a guess and prune strategy that crucially exploits the nature of the robust and stochastic objective. In particular, we guess the worst-case second stage cost and based on the guess, select a subset of costly scenarios for the first-stage solution to address. The second-stage solution for any scenario is simply the min-cut (or shortest path) problem in the residual graph. The key contribution is to show that there is a near-optimal first-stage solution that completely satisfies the subset of costly scenarios that are selected by our procedure. While the guess and prune strategy is not directly applicable for the stochastic versions, we show that using a novel LP formulation, we can adapt a guess and prune algorithm for the stochastic versions. Our algorithms based on the guess and prune strategy provide insights about the applicability of this approach for more general robust and stochastic versions of combinatorial problems.

Keywords
Robust optimization – Combinatorial optimization – Approximation algorithms
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-128017 (URN)10.1007/s10107-013-0742-0 (DOI)
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-05-26
Nikolaevskiy, I., Lukyanenko, A., Polishchuk, T., Polishchuk, V. & Gurtov, A. (2015). isBF: Scalable in-packet bloom filter based multicast. Computer Communications, 70, 79-85
Open this publication in new window or tab >>isBF: Scalable in-packet bloom filter based multicast
Show others...
2015 (English)In: Computer Communications, ISSN 0140-3664, E-ISSN 1873-703X, Vol. 70, p. 79-85Article in journal (Refereed) Published
Abstract [en]

Bloom filter (BF) based forwarding was proposed recently in several protocol alternatives to IP multicast. Some of these protocols avoid the state in intermediate routers and leave the burden of scalability management to the multicast source and end-hosts. Still, the existing BF-based protocols have scalability limitations and require explicit network management as well as non-trivial functionality from the network components. In this work we address the scalability limitations of the BF-based forwarding protocols by partitioning endhosts into clusters. We propose several algorithms to do the partitioning so as to decrease the overall traffic in the network. We evaluate our algorithms in a real Internet topology, demonstrating the ability of the proposed design to save up to 70% of traffic volume in the large-scale topology for big groups of subscribers, and up to 30% for small groups. (C) 2015 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV, 2015
Keywords
In-packet bloom filters; Multicast; Internet; Architecture
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-123074 (URN)10.1016/j.comcom.2015.05.002 (DOI)000364268000007 ()
Available from: 2015-12-04 Created: 2015-12-03 Last updated: 2018-01-10
Kostitsyna, I., Noellenburg, M., Polishchuk, V., Schulz, A. & Strash, D. (2015). On Minimizing Crossings in Storyline Visualizations. In: GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2015: . Paper presented at 23rd International Symposium on Graph Drawing and Network Visualization (GD) (pp. 192-198). SPRINGER INT PUBLISHING AG, 9411
Open this publication in new window or tab >>On Minimizing Crossings in Storyline Visualizations
Show others...
2015 (English)In: GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2015, SPRINGER INT PUBLISHING AG , 2015, Vol. 9411, p. 192-198Conference paper, Published paper (Refereed)
Abstract [en]

In a storyline visualization, we visualize a collection of interacting characters (e. g., in a movie, play, etc.) by x-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with n characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with O(n log n) crossings. Furthermore, we show that there exist storylines in this restricted case that require Omega(n log n) crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixedparameter tractable, when parameterized on the number of characters k. Our algorithm runs in time O(k!(2) k log k+ k!(2) m), where m is the number of meetings.

Place, publisher, year, edition, pages
SPRINGER INT PUBLISHING AG, 2015
Series
Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Civil Engineering
Identifiers
urn:nbn:se:liu:diva-127596 (URN)10.1007/978-3-319-27261-0_16 (DOI)000373628600016 ()978-3-319-27261-0 (ISBN)978-3-319-27260-3 (ISBN)
Conference
23rd International Symposium on Graph Drawing and Network Visualization (GD)
Available from: 2016-05-03 Created: 2016-05-03 Last updated: 2017-07-11
Kostitsyna, I., Loffler, M. & Polishchuk, V. (2015). Optimizing airspace closure with respect to politicians egos. Theoretical Computer Science, 586, 161-175
Open this publication in new window or tab >>Optimizing airspace closure with respect to politicians egos
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 586, p. 161-175Article in journal (Refereed) Published
Abstract [en]

When a president is landing at a busy airport, the airspace around the airport closes for commercial traffic. We show how to schedule the presidential squadron so as to minimize its impact on scheduled civilian flights; to obtain an efficient solution we use a "rainbow" algorithm recoloring aircraft on the fly as they are stored in a special type of forest. We also give a data structure to answer the following query efficiently: Given the presidents ego (the requested duration of airspace closure), when would be the optimal time to close the airspace? Finally, we study the dual problem: Given the time when the airspace closure must start, what is the longest ego that can be tolerated without sacrificing the general traffic? We solve the problem by drawing a Christmas tree in a delay diagram; the tree allows one to solve also the query version of the problem. (C) 2015 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
Elsevier, 2015
Keywords
Scheduling; Data structure; Algorithms
National Category
Civil Engineering
Identifiers
urn:nbn:se:liu:diva-120226 (URN)10.1016/j.tcs.2015.04.014 (DOI)000356751800012 ()
Note

Funding Agencies|Netherlands Organisation for Scientific Research (NWO) [612.001.106, 639.021.123]; Swedens innovation agency VINNOVA [2014-03476]

Available from: 2015-07-21 Created: 2015-07-20 Last updated: 2017-12-04
Organisations

Search in DiVA

Show all publications