This work resolves the optimal average-case cost of the Disk-Inspection problem, a variant of Bellman's 1955 lost-in-a-forest problem. In Disk-Inspection, a mobile agent starts at the center of a unit disk and follows a trajectory that inspects perimeter points whenever the disk does not obstruct visibility. The worst-case cost was solved optimally in 1957 by Isbell, but the average-case version remained open, with heuristic upper bounds proposed by Gluss in 1961 and improved only recently. Our approach applies Fermat's Principle of Least Time to a recently proposed discretization framework, showing that optimal solutions are captured by a one-parameter family of recurrences independent of the discretization size. In the continuum limit these recurrences give rise to a single-parameter optimal control problem, whose trajectories coincide with limiting solutions of the original Disk-Inspection problem. A crucial step is proving that the optimal initial condition generates a trajectory that avoids the unit disk, thereby validating the optics formulation and reducing the many-variable optimization to a rigorous one-parameter problem. In particular, this disproves Gluss's conjecture that optimal trajectories must touch the disk. Our analysis determines the exact optimal average-case inspection cost, equal to $3.549259\ldots$ and certified to at least six digits of accuracy.

• A dynamic trend analysis framework for Stack Exchange communities is introduced. • Two indicators for measuring topic growth are introduced. • A classifier to identify ChatGPT-related questions is introduced. • Tag clustering combining Inclusion Index with Affinity Propagation is used. • An overhauled visualization tool from our previous work is presented. Technological and methodological trends emerge at unprecedented rates, attracting developers to explore their potential and seek advice in online social networks. In this spectrum, ChatGPT has become a popular technology used for generating content to satisfy user queries while developers also integrate its mechanisms into their applications. Social networks usually revolve around technological trends through relevant announcements, posts, and questions. The primary goal is to demystify and evaluate the content surrounding questions from developers on Stack Overflow (SO) regarding a trending technology or method, in this case, ChatGPT. We present a topic-oriented trend analysis framework for analyzing questions from Stack Exchange communities, formulating a case study with five Research Questions (RQs) adapted to ChatGPT-related queries posted on Stack Overflow. The proposed framework contains different components aimed at extracting the main topics of relevant questions, providing analytics and pipelines for evaluating and comparing topic popularity, difficulty, and trending ability, as well as filtering irrelevant questions. The analysis uncovers diverse topics referring to technologies, platforms, and programming languages associated with ChatGPT usage, as well as a variety of purposes related to textual, audio, and image data. Additionally, the framework helped in identifying one popular and one unpopular topic, along with one difficult and four rising topics. In the context of ChatGPT, statistical tests indicated that Langchain is a more popular framework than Flutter and that questions related to the ChatGPT API concentrate lower scores but more answers than questions associated with LLMs. Overall, this paper demonstrates that the introduced framework can be utilized for studying multiple objectives covering a trending subject, as its mechanisms rely exclusively on the standard characteristics of Stack Exchange (SE) questions. Also, the methodologies and findings can offer insights and ideas for future research and experiments.

The input to the Triangle Evacuation problem is a triangle ABC . Given a starting point S on the perimeter of the triangle, a feasible solution to the problem consists of two unit-speed trajectories of mobile agents that eventually visit every point on the perimeter of ABC . The cost of a feasible solution (evacuation cost) is defined as the supremum over all points T of the time it takes that T is visited for the first time by an agent plus the distance of T to the other agent at that time. Similar evacuation type problems are well studied in the literature covering the unit circle, the ℓ p unit circle for p ≥ 1 , the square, and the equilateral triangle. We extend this line of research to arbitrary non-obtuse triangles. Motivated by the lack of symmetry of our search domain, we introduce 4 different algorithmic problems arising by letting the starting edge and/or the starting point S on that edge to be chosen either by the algorithm or the adversary. To that end, we provide a tight analysis for the algorithm that has been proved to be optimal for the previously studied search domains, as well as we provide lower bounds for each of the problems. Both our upper and lower bounds match and extend naturally the previously known results that were established only for equilateral triangles.

We study weighted group search on a disk , where two unit-speed agents must locate a hidden target exactly distance 1 away (within a unit-radius disk), starting from the same point. Agents share findings instantly via the wireless model. The goal is to minimize the worst-case weighted average of their arrival times, with one agent weighted 1 and the other w ∈ [ 0 , 1 ] . This problem extends prior work on search on a line (with known optimal strategies) and the priority evacuation problem, which corresponds to w = 0 and still has a notable gap between upper and lower bounds. Our contributions are the following: (1) Upper bounds for all w , using refined known techniques. (2) A novel lower-bound framework using linear programming, inspired by metric embeddings, and (3) Improved bounds for priority evacuation, raising the lower bound from 4.38962 to 4.56798.

As society is continuously adapting to technological change and progress, fast-moving digital transformations are the driving force for setting the necessary skillsets for the workforce. Furthermore, the advent of Industry 5.0 as a defining concept for the future, which advocates a human-centric coalescence of humans and technology or software, renders the skilled workforce the most important asset in any organization or business. The endgame of the digital transformation is to evoke the reshaping, evolution, or replacement of traditional and possibly obsolete processes at intra- or inter-organizational levels in multiple aspects, introducing innovative ways of re-defining the workforce. In this context SKILLAB will act as a smart tool for handling, honing, and widening the competencies of the personnel of companies, forecasting future skill gaps and providing European citizens with a tool for upskilling and reskilling.

This research focuses on improving the fine-tuning process of self-supervised learning models for remote sensing, particularly the Cross-Scale Masked Auto-Encoder (MAE). We tackle the challenges of intricate, multi-source imagery and present advancements in adapting the Cross-Scale MAE for diverse remote sensing environments. Our contributions include methods for handling complex dataset dimensions and semantic diversity, demonstrating the model’s adaptability and expanding its application scope in remote sensing.

In terms of monitoring and managing anthropogenic activities, accurately identifying the distinct phases in construction projects using satellite imagery remains a challenging task. In this paper, we reformulate the phase classification problem into a transition detection problem and introduce a novel Koopman-based Transition Detection (KTD) method, which applies Koopman operator theory to analyze the nonlinear dynamics of material histograms in a linear framework. KTD employs a sliding window to perform Dynamic Mode Decomposition (DMD) on the time-series material histograms and detects the transition point by analyzing the movement of the eigenvalue in consecutive strides. Compared to CNN-based methods, our proposed KTD method demonstrates enhanced accuracy and reduced temporal error in phase identification. Furthermore, as an unsupervised method that does not require large amounts of training data, it shows a better generalization capability in the sequestered region.

With medical technological advances being developed in a rapid pace, the need for effective Scientific Software Development (SSD), that can process, store and visualize medical data is ever growing. Particularly during the COVID-19 pandemic, the medical community came together to produce efficient solutions to tackle this global setback. Programmers and developers have an active role in the procurement of medical software, with many of them exchanging knowledge and opinions in Q&A portals like Stack Overflow (SO) about methodologies, techniques and programming queries. In this study we present a data-driven framework that collects, filters, stores and analyzes issues and questions for medical applications from SO, visualizing them in an intuitive manner. To highlight the functionalities of our framework, we present a case study with COVID-19 SSD related questions, providing insights and valuable information about the status of the domain.

Vehicular Cloud Computing (VCC) is a collective of vehicles capable of sharing information and various resources, such as computation power, storage, and bandwidth among drivers. The resources available in the vehicular cloud can also be shared over the network as on-demand services, allowing users to access and utilize them as needed. Security and privacy stand out as key challenges in VCC. Maintaining the confidentiality, integrity, and availability of data and services within this frame-work while safeguarding the privacy of users and their sensitive information poses significant hurdles to be addressed. One of the solutions to address security and privacy in VCC is using trust based authentication approach. Trust-based authentication algorithm relies on past transactions and feedback from vehicles to calculate the trust degree. By analyzing historical interactions and evaluating the reliability and credibility of each vehicle based on their past behavior, the algorithm can determine the level of trustworthiness of a particular vehicle. In this model, certain responsible overseers are present within each cluster, and their role involves monitoring the behavior of individual vehicles. In our work we use comprehensive set of simulations to evaluate the effectiveness of trust based authentication in Vehicular Cloud Computing. We concentrate on the impact of the overseers in different clusters. By studying their role and behavior, we can gain insights into the effectiveness of cluster management and optimize the system's efficiency.

Remote sensing images present unique challenges to image analysis due to the extensive geographic coverage, hardware limitations, and misaligned multi-scale images. This paper revisits the classical multi-scale representation learning prob- lem but under the general framework of self-supervised learning for remote sensing image understanding. We present Cross-Scale MAE, a self-supervised model built upon the Masked Auto-Encoder (MAE). During pre-training, Cross-Scale MAE employs scale augmentation techniques and enforces cross-scale consistency constraints through both contrastive and generative losses to ensure consistent and meaningful representations well-suited for a wide range of downstream tasks. Further, our implementation leverages the xFormers library to accelerate network pre-training on a single GPU while maintaining the quality of learned represen- tations. Experimental evaluations demonstrate that Cross-Scale MAE exhibits superior performance compared to standard MAE and other state-of-the-art remote sensing MAE methods.

Semantic segmentation in large-scale aerial images is an extremely challenging task. On one hand, the limited ground truth, as compared to the vast area the images cover, greatly hinders the development of supervised representation learning. On the other hand, the large footprint from remote sensing raises new challenges for semantic segmentation. In addition, the complex and ever changing image acquisition conditions further complicate the problem where domain shifting commonly occurs. In this paper, we exploit self-supervised contrastive learning (CL) methodologies for semantic segmentation in aerial imagery. In addition to performing CL at the feature level as most practices do, we add another level of contrastive learning, at the semantic level, taking advantage of the segmentation output from the downstream task. Further, we embed local mutual information in the semantic-level CL to enforce local consistency. This has largely enhanced the representation power at each pixel and improved the generalization capacity of the trained model. We refer to the proposed approach as multi-level contrastive learning with local consistency (mCL-LC). The experimental results on different benchmarks indicate that the proposed mCL-LC exhibits superior performance as compared to other state-of-the-art contrastive learning frameworks for the semantic segmentation task. mCL-LC also carries better generalization capacity especially when domain shifting exists.

Worldwide up to May 2022 there have been 515 million cases of COVID-19 infection and over 6 million deaths. The World Health Organization estimated that 115,000 healthcare workers died from COVID-19 from January 2020 to May 2021. This toll on human lives prompted this review on 5G based networking primarily on major components of healthcare delivery: diagnosis, patient monitoring, contact tracing, diagnostic imaging tests, vaccines distribution, emergency medical services, telesurgery and robot-assisted tele-ultrasound. The positive impact of 5G as core technology for COVID-19 applications enabled exchange of huge data sets in fangcang (cabin) hospitals and real-time contact tracing, while the low latency enhanced robot-assisted tele-ultrasound, and telementoring during ophthalmic surgery. In other instances, 5G provided a supportive technology for applications related to COVID-19, e.g., patient monitoring. The feasibility of 5G telesurgery was proven, albeit by a few studies on real patients, in very low samples size in most instances. The important future applications of 5G in healthcare include surveillance of elderly people, the immunosuppressed, and nano- oncology for Internet of Nano Things (IoNT). Issues remain and these require resolution before routine clinical adoption. These include infrastructure and coverage; health risks; security and privacy protection of patients' data; 5G implementation with artificial intelligence, blockchain, and IoT; validation, patient acceptance and training of end-users on these technologies.

As the industry is moving towards digitalized solutions and practices, a growth in remote working has been observed with companies embracing flexibility for their workforce. Global crises, such as the coronavirus pandemic, have also accelerated this process, transforming the labor market. This trend is reflected in job portals, that contain an increasing number of remote job advertisements. Recognizing this evolving change, we perform a thorough study in Stack Overflow, to examine the main characteristics of remote working that discriminate it from its on-site counterpart. By collecting and analyzing 8514 job posts and leveraging text mining and graph theory methodologies, we attempt to pinpoint the primary elements that define each category, from dominant technologies to job positions and top seeking industries. The findings suggest that remote working presents differences from traditional working, being mainly associated with the software engineering sector and with well-known software development and data analytics technologies.

The Covid-19 outbreak has changed to an unprecedented extent almost every aspect of human activity. At the same time, the pandemic has stimulated enormous amount of research by scientists across various disciplines, seeking to study the phenomenon itself, its epidemiological characteristics and ways to confront its consequences. Information Technology, and particularly Data Science, drive innovation in all related to Covid-19 biomedical fields. Acknowledging that software developers routinely resort to open `question & answer' communities like Stack Overflow to seek advice on solving technical issues, we have performed an empirical study to investigate the extent, evolution and characteristics of Covid-19 related posts. Through the study of 464 Stack Overflow questions posted in February and March 2020 and leveraging the power of text mining, we attempt to shed light into the interest of developers in Covid-19 related topics and the most popular problems for which the users seek information. The findings reveal that indeed this global crisis sparked off an intense activity in Stack Overflow with most post topics reflecting a strong interest on the analysis of Covid- 19 data, primarily using Python technologies.

Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of $d$, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least $9d-o(d)$. It was shown recently that $k\geq2$ robots traveling at unit speed also require at least $9d$ group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance $x$ at constant speed $s$ is given by $s^2 x$. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple $c$ of the distance $d$ and the speed of the robots is bounded by $b$. Motivation for this study is that for the case when robots must complete the search in $9d$ time with maximum speed one, a single robot requires at least $9d$ energy, while for two robots, all previously proposed algorithms consume at least $28d/3$ energy. When the robots have bounded memory, we generalize existing algorithms to obtain a family of optimal (and in some cases nearly optimal) algorithms parametrized by pairs of $b,c$ values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. We also propose a novel search algorithm, with unbounded memory, that simultaneously achieves search time $9d$ and consumes energy $8.42588d$. Our result shows that two robots can search on the line in optimal time $9d$ while consuming less total energy than a single robot within the same search time.

Searching for a line on the plane with n unit speed robots is a classic online problem that dates back to the 50’s, and for which competitive ratio upper bounds are known for every n ≥ 1, see [Baeza-Yates and Schott, 1995]. In this work we improve the best lower bound known for n=2 robots [Baeza-Yates and Schott, 1995] from 1.5993 to 3. Moreover we prove that the competitive ratio is at least √{3} for n=3 robots, and at least 1/cos ({π/n}) for n ≥ 4 robots. Our lower bounds match the best upper bounds known for n ≥ 4, hence resolving these cases. To the best of our knowledge, these are the first lower bounds proven for the cases n ≥ 3 of this several decades old problem.

We initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions on the perimeter of a disk and at known arc distance. A team of two robots start from the center of the disk, and their goal is to fetch the treasure to the exit. At any time the robots can move anywhere they choose on the disk, independently of each other, with the same speed. A robot detects an interesting point (treasure or exit) only if it passes over the exact location of that point. We are interested in designing distributed algorithms that minimize the worst-case treasure-evacuation time, i.e. the time it takes for the treasure to be discovered and brought (fetched) to the exit by any of the robots. The communication protocol between the robots is either wireless, where information is shared at any time, or face-to-face (i.e. non-wireless), where information can be shared only if the robots meet. For both models we obtain upper bounds for fetching the treasure to the exit. Our main technical contribution pertains to the face-to-face model. More specifically, we demonstrate how robots can exchange information without meeting, effectively achieving a highly efficient treasure-evacuation protocol which is minimally affected by the lack of distant communication. Finally, we complement our positive results above by providing a lower bound in the face-to-face model.

Abstract. A fence, represented by a unit interval is to be patrolled collectively by n robots. At any moment a robot may move in one of the two possible states: walking or patrolling. Each state is associated with a maximal moving speed which cannot be exceeded. A robot may have a unique pair of speeds, but its patrolling speed is always smaller than its walking speed. Each robot is allowed to patrol while moving only in one of the two directions (not necessarily the same for all robots). We want to schedule the perpetual movements of the robots so as to minimize the idleness, defined as the smallest time interval within which every point is always visited by some robot. First, we give a centralized algorithm constructing schedules with optimal idleness, and subsequently we show a nice application to a transportation problem concerning Scheduling with Regular Delivery. Our main contribution is the study of distributed, dynamical schedules for patrolling robots with only primitive capabilities. Surprisingly we are able to design a dynamic schedule for very weak collections of two robots (silent, oblivious, passively mobile), achieving the optimal idleness. Our algorithm defines a dynamical system of memoryless robots moving back and forth in an interval. In general, analysis of the system dynamics is very complex. Part of our contribution is a very technical analysis of the dynamics of special families of dynamical systems of n robots that we call regular. For such systems we also propose a highly non-trivial O(n2) algorithm to decide whether or not robots converge to a stable configuration thus verifying if the dynamic schedule is optimal. It turns out that a very natural family of

We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of S_d (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.

Recently, Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the M ax B isection problem. We improve their algorithm to a 0.8776-approximation. As M ax B isection is hard to approximate within α GW + ε ≈ 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that M ax B isection is approximable within α GW − ε, that is, that the bisection constraint (essentially) does not make M ax C ut harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of M ax 2-S at . Our approximation ratio for this problem exactly matches the optimal approximation ratio for M ax 2-S at , that is, α LLZ + ε ≈ 0.9401, showing that the bisection constraint does not make M ax 2-S at harder. This improves on a 0.93-approximation for this problem from Raghavendra and Tan.

We study integrality gap (IG) lower bounds on strong LP and SDP relaxations derived by the Sherali-Adams (SA), Lovász-Schrijver-SDP (LS_+), and Sherali-Adams-SDP (SA_+) lift-and-project (L&P) systems for the t-Partial-Vertex-Cover (t-PVC) problem, a variation of the classic Vertex-Cover problem in which only t edges need to be covered. t-PVC admits a 2-approximation using various algorithmic techniques, all relying on a natural LP relaxation. Starting from this LP relaxation, our main results assert that for every epsilon>0, level-Theta(n) LPs or SDPs derived by all known L&P systems that have been used for positive algorithmic results (but the Lasserre hierarchy) have IGs at least (1-epsilon)n/t, where n is the number of vertices of the input graph. Our lower bounds are nearly tight, in that level-n relaxations, even of the weakest systems, have integrality gap 1. As lift-and-project systems have given the best algorithms known for numerous combinatorial optimization problems, our results show that restricted yet powerful models of computation derived by many L&P systems fail to witness c-approximate solutions to t-PVC for any constant c, and for t=O(n). This is one of the very few known examples of an intractable combinatorial optimization problem for which LP-based algorithms induce a constant approximation ratio, still lift-and-project LP and SDP tightenings of the same LP have unbounded IGs. As further motivation for our results, we show that the SDP that has given the best algorithm known for t-PVC has integrality gap n/t on instances that can be solved by the level-1 LP relaxation derived by the LS system. This constitutes another rare phenomenon where (even in specific instances) a static LP outperforms an SDP that has been used for the best approximation guarantee for the problem at hand. Finally, we believe our results are of independent interest as they are among the very few known integrality gap lower bounds for LP and SDP 0-1 relaxations in which not all variables possess the same semantics in the underlying combinatorial optimization problem. Most importantly, one of our main contributions is that we make explicit of a new and simple methodology of constructing solutions to LP relaxations that almost trivially satisfy constraints derived by all SDP L&P systems known to be useful for algorithmic positive results (except the La system). The latter sheds some light as to why La tightenings seem strictly stronger than LS_+ or SA_+ tightenings.

Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the Max Bisection problem. We improve their algorithm to a 0.8776-approximation. As Max Bisection is hard to approximate within $\alpha_{GW} + \epsilon \approx 0.8786$ under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that Max Bisection is approximable within $\alpha_{GW}-\epsilon$, i.e., the bisection constraint (essentially) does not make Max Cut harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of Max 2-Sat. Our approximation ratio for this problem exactly matches the optimal approximation ratio for Max 2-Sat, i.e., $\alpha_{LLZ} + \epsilon \approx 0.9401$, showing that the bisection constraint does not make Max 2-Sat harder. This improves on a 0.93-approximation for this problem due to Raghavendra and Tan.

We consider the design of strategyproof cost-sharing mechanisms. We give two simple, but extremely versatile, black-box reductions, that in combination reduce the cost-sharing mechanism-design problem to the algorithmic problem of finding a minimum-cost solution for a set of players. Our first reduction shows that any truthful, α-approximation mechanism for the social-cost minimization (SCM) problem satisfying a technical no-bossiness condition can be morphed into a truthful mechanism that achieves an O(α log n)-approximation where the prices recover the cost incurred. Thus, we decouple the task of truthfully computing an outcome with near-optimal social cost from the cost-sharing problem. This is fruitful since truthful mechanism-design, especially for single-dimensional problems, is a relatively well-understood and manageable task. Our second reduction nicely complements the first one by showing that any LP-based ρ-approximation for the problem of finding a min-cost solution for a set of players yields a truthful, no-bossy, (ρ + 1)-approximation for the SCM problem (and hence, a truthful (ρ + 1)log n-approximation cost-sharing mechanism). These reductions find a slew of applications, yielding, as corollaries, the first or improved polytime cost-sharing mechanisms for a variety of problems. For example, our first reduction coupled with the celebrated VCG mechanism shows that for any cost-sharing problem (with a monotone cost function) one can obtain a truthful mechanism that achieves an O(log n)-approximation where the prices recover the cost incurred. Other applications include O(log n)-approximation mechanisms for: survivable network design problems, facility location (FL) problems including capacitated and connected FL problems, and minimum-makespan scheduling on unrelated machines. Our results demonstrate that in contrast with our current understanding of group-strategyproof and acyclic mechanisms, strategyproofness allows for ample flexibility in cost-sharing mechanism design enabling one to effectively leverage various algorithmic results.

We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality gap 2-\epsilon. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new tool to establish Local-Global Discrepancy which uses simple facts from high-dimensional geometry. This allows us to give Sherali-Adams solutions with objective value n(1/2+o(1)) for graphs with small (2+o(1)) vector chromatic number. Since such graphs with no linear size independent sets exist, this immediately gives a tight integrality gap for the Sherali-Adams system for superconstant number of tightenings. In order to obtain a Sherali-Adams solution that also satisfies semidefinite conditions, we reduce semidefiniteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs.

Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for Max Cut and Sparsest Cut use semidefinite programming. Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is Vertex Cover. Probabilistically checkable proof (PCP)-based techniques of Dinur and Safra [Ann. of Math./ (2), 162 (2005), pp. 439–486] show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. There is a widespread belief that semidefinite programming (SDP) techniques are the most promising methods available for improving upon this factor of 2. Following a line of study initiated by Arora et al. [Theory Comput., 2 (2006), pp. 19–51], our aim is to show that a large family of linear programming (LP)- and SDP-based algorithms fail to produce an approximation for Vertex Cover better than 2. Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166–190] introduced the systems $LS$ and $LS_+$ for systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, $LS_+$ captures the celebrated SDP-based algorithms for Max Cut and Sparsest Cut mentioned above. We rule out polynomial-time SDP-based $2-\Omega(1)$ approximations for Vertex Cover using $LS_+$. In particular, for every $\epsilon>0$ we prove an integrality gap of $2-\epsilon$ for Vertex Cover SDPs obtained by tightening the standard LP relaxation with $\Omega(\sqrt{\log n/\log\log n})$ rounds of $LS_+$. While tight integrality gaps were known for Vertex Cover in the weaker $LS$ system [G. Schoenebeck, L. Trevisan, and M. Tulsiani, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2007, pp. 302–310], previous results did not rule out a $2-\Omega(1)$ approximation after even two rounds of $LS_+$.

We show that the integrality gap of the standard SDP for \vc~on instances of $n$ vertices remains $2-o(1)$ even after the addition of \emph{all} hypermetric inequalities. Our lower bound requires new insights into the structure of SDP solutions behaving like $\ell_1$ metric spaces when one point is removed. We also show that the addition of all $\ell_1$ inequalities eliminates any solutions that are not convex combination of integral solutions. Consequently, we provide the strongest possible separation between hypermetrics and $\ell_1$ inequalities with respect to the tightening of the standard SDP for \vc.

Jylab is a PSE architecture emphasizing portable computing over distributed platforms. It captures the idea of reusing some of the best open source software projects' functionality within the context of a single, net-aware, interactive environment. The original implementation of this idea resulted in a system built around a portable interpreter supported by a carefully selected suite of libraries spanning a comprehensive set of applications including scripting, numerical linear algebra, distributed/grid computing and Internet algorithmics. Because Jylab is a multicomponent PSE system, it is quite natural to base its implementation on a robust platform automating the management of complex stacks of software components, i.e. self-describing objects. The Eclipse platform meets this basic prerequisite, additionally providing many other interesting integration facilities, an extensive set of ready-to-use plug-ins and is also embraced by a vibrant community of users, developers and leading software companies. In this paper we describe the design and basic implementation of a flexible environment resulting from the integration of Jylab into Eclipse. To this effect, we survey relevant aspects of the rich Eclipse ecosystem as well as the Jylab approach to PSE construction. To illustrate our environment we present case studies from grid computing, neural network training and native libraries integration.

Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for Max Cut and Sparsest Cut use semidefinite programming. Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is Vertex Cover. PCP-based techniques of Dinur and Safra [7] show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. Furthermore, there is a widespread belief that SDP technicptes are the most promising methods available for improving upon this factor of 2. Following a line of study initiated by Arora et al. [3], our aim is to show that a large family of LP and SDP based algorithms fail to produce an approximation for Vertex Cover better than 2. Lovasz and Schrijver [21] introduced the systems LS and LS+for systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, LS+captures the celebrated SDP-based algorithms for Max Cur and Sparsest Cur mentioned above. We rule out polynomial-time 2 - Omega(lfloor) approximations for Vertex Cover using LS+. In particular, we prove an integrality gap of 2 - o(lfloor)for Vertex Cover SDPs obtained by tightening the standard LP relaxation with Omega(radiclog n/ log log n) rounds of LS+. While tight integrality gaps were known for Vertex Cover in the weaker LS system [23 ], previous results did not rule out a2 - Omega(1) approximation after even two rounds of LS+.