NDLI: Improved algorithms for orienteering and related problems

Please wait, while we are loading the content...

ACM Transactions on Algorithms (TALG) : Volume 13

ACM Transactions on Algorithms (TALG) : Volume 12

ACM Transactions on Algorithms (TALG) : Volume 11

ACM Transactions on Algorithms (TALG) : Volume 10

ACM Transactions on Algorithms (TALG) : Volume 9

ACM Transactions on Algorithms (TALG) : Volume 8

Issue 4, September 2012

Issue 3, July 2012

Assignment problem in content distribution networks: Unsplittable hard-capacitated facility location

Expansion properties of (secure) wireless networks

I/O-efficient shortest path algorithms for undirected graphs with random or bounded edge lengths

Improved algorithms for orienteering and related problems

Santa claus meets hypergraph matchings

The speed of convergence in congestion games under best-response dynamics

Polynomial-time algorithms for minimum energy scheduling

Tight approximation algorithms for scheduling with fixed jobs and nonavailability

Scalably scheduling processes with arbitrary speedup curves

Entropy, triangulation, and point location in planar subdivisions

Smoothed analysis of left-to-right maxima with applications

Counting occurrences for a finite set of words: Combinatorial methods

Testing nilpotence of galois groups in polynomial time

Issue 2, April 2012

Issue 1, January 2012

ACM Transactions on Algorithms (TALG) : Volume 7

ACM Transactions on Algorithms (TALG) : Volume 6

ACM Transactions on Algorithms (TALG) : Volume 5

ACM Transactions on Algorithms (TALG) : Volume 4

ACM Transactions on Algorithms (TALG) : Volume 3

ACM Transactions on Algorithms (TALG) : Volume 2

ACM Transactions on Algorithms (TALG) : Volume 1

Improved algorithms for orienteering and related problems

Content Provider	ACM Digital Library
Author	Chekuri, Chandra Pál, Martin Korula, Nitish
Copyright Year	2012
Abstract	In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph $\textit{G}=(\textit{V,$ E) (directed or undirected), two nodes s, t ∈ $\textit{V}$ and a time limit $\textit{B},$ find an $\textit{s}-\textit{t}$ $\textit{walk}$ in $\textit{G}$ of total length at most $\textit{B}$ that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as $\textit{k}-MST.$ Orienteering with $\textit{time-windows}$ is the more general problem in which each node $\textit{v}$ has a specified time-window $[\textit{R}(\textit{v}),$ $\textit{D}(\textit{v})]$ and a node $\textit{v}$ is counted as visited by the walk only if $\textit{v}$ is visited during its time-window. We design new and improved algorithms for the orienteering problem and orienteering with time-windows. Our main results are the following: — A (2+ε) approximation for orienteering in undirected graphs, improving upon the 3-approximation of Bansal et al. [2004]. — An $O(log^{2}$ OPT) approximation for orienteering in directed graphs, where OPT ≤ $\textit{n}$ is the number of vertices visited by an optimal solution. Previously, only a quasipolynomial-time algorithm due to Chekuri and Pál [2005] achieved a polylogarithmic approximation (a ratio of $\textit{O}(log$ OPT)). — Given an α approximation for orienteering, we show an $\textit{O}(α$ ċ max{log OPT, log $l_{max}/l_{min}})$ approximation for orienteering with time-windows, where $l_{max}$ and $l_{min}$ are the lengths of the longest and shortest time-windows respectively.
Starting Page	1
Ending Page	27
Page Count	27
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/2229163.2229167
Volume Number	8
Issue Number	3
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-24
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	$\textit{k}-stroll$ Approximation algorithms Orienteering Orienteering with time-windows
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Approximation Algorithms for Min-Max Generalization Problems

A Constant Factor Approximation Algorithm for Fault-Tolerant $\textit{k}-Median$

Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

Approximation Algorithms and Hardness of the $textit{k}-Route$ Cut Problem (TALG, Vol.12, Issue 1)

Approximation Algorithms for Orienteering with Time Windows

Approximation algorithms for the directed k-tour and k-stroll problems.

Improved algorithms for orienteering and related problems.

Fault-tolerant facility location

Fixed-parameter algorithms for $(\textit{k},$ $\textit{r})-center$ in planar graphs and map graphs

Improved algorithms for orienteering and related problems

Similar Documents

Approximation Algorithms for Min-Max Generalization Problems

A Constant Factor Approximation Algorithm for Fault-Tolerant $\textit{k}-Median$

Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

Approximation Algorithms and Hardness of the $textit{k}-Route$ Cut Problem (TALG, Vol.12, Issue 1)

Approximation Algorithms for Orienteering with Time Windows

Approximation algorithms for the directed k-tour and k-stroll problems.

Improved algorithms for orienteering and related problems.

Fault-tolerant facility location

Fixed-parameter algorithms for $(\textit{k},$ $\textit{r})-center$ in planar graphs and map graphs

Improved algorithms for orienteering and related problems