Subscribe
Follow Us
Publication

New instances for maximum weight independent set from a vehicle routing application

By Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G. C. Resende, Quico Spaen
2021
Download Copy BibTeX
Share
Download
Copy BibTeX
Share
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve in part because of their large size. We present instances with up to 881 thousand nodes and 383 million edges.
Research areas

Latest news

Work with us

See more jobs See more jobs
Applied Scientist, Amazon
US, CA, Sunnyvale
At Amazon Fashion, we are obsessed with making Amazon Fashion the most loved fashion destinations globally. We're searching for Computer Vision pioneers who are passionate about technology, innovation, and customer experience, and who are enthusiastic about making a lasting impact on the industry. You'll be working with talented scientists, engineers, and product managers to innovate on behalf of our customers. If you're fired up about being part of a dynamic, driven team, then this is your moment to join us on this exciting journey and change the world of eCommerce forever Key job responsibilities As a Applied Scientist, you will be at the forefront to define, own and drive the science that span multiple machine learning models and enabling multiple product/engineering teams and organizations. You will partner with product management and technical leadership to identify opportunities to innovate customer facing experiences. You will identify new areas of investment and work to align product roadmaps to deliver on these opportunities. As a science leader, you will not only develop unique scientific solutions, but more importantly influence strategy and outcomes across different Amazon organizations such as Search, Personalization and more. This role is inherently cross-functional and requires a strong ability to communicate, influence and earn the trust of software engineers, technical and business leadership. We are open to hiring candidates to work out of one of the following locations: Sunnyvale, CA, USA
Applied Scientist
GB, Cambridge
Our team undertakes research together with multiple organizations to advance the state-of-the-art in speech technologies. We not only work on giving Alexa, the ground-breaking service that powers Echo, her voice, but we also develop cutting-edge technologies with Amazon Studios, the provider of original content for Prime Video. Do you want to be part of the team developing the latest technology that impacts the customer experience of ground-breaking products? Then come join us and make history. We are looking for a passionate, talented, and inventive Senior Applied Scientist with a background in Machine Learning to help build industry-leading Speech, Language and Video technology. As a Senior Applied Scientist at Amazon you will work with talented peers to develop novel algorithms and modelling techniques to drive the state of the art in speech and vocal arts synthesis. Position Responsibilities: - Participate in the design, development, evaluation, deployment and updating of data-driven models for digital vocal arts applications. - Participate in research activities including the application and evaluation and digital vocal and video arts techniques for novel applications. - Research and implement novel ML and statistical approaches to add value to the business. - Mentor junior engineers and scientists. We are open to hiring candidates to work out of one of the following locations: Cambridge, GBR
Intern - Economics, PXT Central Science
US, WA, Seattle
The Amazon Economics Team is hiring Economist Interns. We are looking for detail-oriented, organized, and responsible individuals who are eager to learn how to work with large and complicated data sets to solve real-world business problems. Some knowledge of econometrics, as well as basic familiarity with Stata, R, or Python is necessary. Experience with SQL, UNIX, Sawtooth, and Spark would be a plus. These are full-time positions at 40 hours per week, with compensation being awarded on an hourly basis. You will learn how to build data sets and perform applied econometric analysis at Internet speed collaborating with economists, data scientists and MBAʼs. These skills will translate well into writing applied chapters in your dissertation and provide you with work experience that may help you with future job market placement. Roughly 85% of interns from previous cohorts have converted to full-time economics employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com. We are open to hiring candidates to work out of one of the following locations: Seattle, WA, USA
Senior Economist, Amazon Advertising Impact Team
US, WA, Seattle
Amazon Advertising Impact Team is looking for a Senior Economist to help translate cutting-edge causal inference and machine learning research into production solutions. The individual will have the opportunity to shape the technical and strategic vision of a highly ambiguous problem space, and deliver measurable business impacts via cross-team and cross-functional collaboration. Amazon is investing heavily in building a world class advertising business. Our advertising products are strategically important to Amazon’s Retail and Marketplace businesses for driving long-term growth. The mission of the Advertising Impact Team is to make our advertising products the most customer-centric in the world. We specialize in measuring and modeling the short- and long-term customer behavior in relation to advertising, using state of the art econometrics and machine learning techniques. With a broad mandate to experiment and innovate, we are constantly advancing our experimentation methodology and infrastructure to accelerate learning and scale impacts. We are highly motivated, collaborative and fun-loving with an entrepreneurial spirit and bias for action. Key job responsibilities • Function as a technical leader to shape the strategic vision and the science roadmap of a highly ambiguous problem space • Develop economic theory and deliver econometrics and machine learning models to optimize advertising strategies on behalf of our customers • Design, execute, and analyze experiments to verify the efficacy of different scientific solutions in production • Partner with cross-team technical contributors (scientists, software engineers, product managers) to implement the solution in production • Write effective business narratives and scientific papers to communicate to both business and technical audience, including the most senior leaders of the company We are open to hiring candidates to work out of one of the following locations: New York, NY, USA | Seattle, WA, USA
Senior Applied Scientist, Sponsored Products
US, NY, New York
Amazon is investing heavily in building a world-class advertising business, and we are responsible for defining and delivering a collection of self-service performance advertising products that drive discovery and sales. We deliver billions of ad impressions and millions of clicks daily and break fresh ground to create world-class products. We are highly motivated, collaborative, and fun-loving with an entrepreneurial spirit and bias for action. With a broad mandate to experiment and innovate, we are growing at an unprecedented rate with a seemingly endless range of new opportunities. Our systems and algorithms operate on one of the world's largest product catalogs, matching shoppers with advertised products with a high relevance bar and strict latency constraints. Sponsored Products Detail Page Blended Widgets team is chartered with building novel product recommendation experiences. We push the innovation frontiers for our hundreds of millions of customers WW to aid product discovery while helping shoppers to find relevant products easily. Our team is building differentiated recommendations that highlight specific characteristics of products (either direct attributes, inferred or machine learned), and leveraging generative AI to provide interactive shopping experiences. We are looking for a Senior Applied Scientist who can delight our customers by continually learning and inventing. Our ideal candidate is an experienced Applied Scientist who has a track-record of performing deep analysis and is passionate about applying advanced ML and statistical techniques to solve real-world, ambiguous and complex challenges to optimize and improve the product performance, and who is motivated to achieve results in a fast-paced environment. The position offers an exceptional opportunity to grow your technical and non-technical skills and make a real difference to the Amazon Advertising business. As a Senior Applied Scientist on this team, you will: * Be the technical leader in Machine Learning; lead efforts within this team and collaborate across teams * Rapidly design, prototype and test many possible hypotheses in a high-ambiguity environment, perform hands-on analysis and modeling of enormous data sets to develop insights that improve shopper experiences and merchandise sales * Drive end-to-end Machine Learning projects that have a high degree of ambiguity, scale, complexity. * Build machine learning models, perform proof-of-concept, experiment, optimize, and deploy your models into production; work closely with software engineers to assist in productionizing your ML models. * Establish scalable, efficient, automated processes for large-scale data analysis, machine-learning model development, model validation and serving. * Research new and innovative machine learning approaches. * Promote the culture of experimentation and applied science at Amazon Team video https://youtu.be/zD_6Lzw8raE We are also open to consider the candidate in Seattle, or Palo Alto. We are open to hiring candidates to work out of one of the following locations: New York, NY, USA
Senior Applied Scientist, Amazon
US, VA, Arlington
Amazon Advertising is one of Amazon's fastest growing and most profitable businesses, responsible for defining and delivering a collection of advertising products that drive discovery and sales. As a core product offering within our advertising portfolio, Sponsored Products (SP) helps merchants, retail vendors, and brand owners succeed via native advertising, which grows incremental sales of their products sold through Amazon. The SP team's primary goals are to help shoppers discover new products they love, be the most efficient way for advertisers to meet their business objectives, and build a sustainable business that continuously innovates on behalf of customers. Our products and solutions are strategically important to enable our Retail and Marketplace businesses to drive long-term growth. We deliver billions of ad impressions and millions of clicks and break fresh ground in product and technical innovations every day! The Search Sourcing and Relevance team parses billions of ads to surface the best ad to show to Amazon shoppers. The team strives to understand customer intent and identify relevant ads that enable them to discover new and alternate products. This also enables sellers on Amazon to showcase their products to customers, which may, at times, be buried deeper in the search results. By showing the right ads to customers at the right time, this team improves the shopper experience, increase advertiser ROI, and improves long-term monetization. This is a talented team of machine learning scientists and software engineers working on complex solutions to understand the customer intent and present them with ads that are not only relevant to their actual shopping experience but also non-obtrusive. This area is of strategic importance to Amazon Retail and Marketplace business, driving long term growth. Key job responsibilities As a Senior Applied Scientist on this team, you will: - Be the technical leader in Machine Learning; lead efforts within this team and across other teams. - Perform hands-on analysis and modeling of enormous data sets to develop insights that increase traffic monetization and merchandise sales, without compromising the shopper experience. - Drive end-to-end Machine Learning projects that have a high degree of ambiguity, scale, complexity. - Build machine learning models, perform proof-of-concept, experiment, optimize, and deploy your models into production; work closely with software engineers to assist in productionizing your ML models. - Run A/B experiments, gather data, and perform statistical analysis. - Establish scalable, efficient, automated processes for large-scale data analysis, machine-learning model development, model validation and serving. - Research new and innovative machine learning approaches. - Recruit Applied Scientists to the team and provide mentorship. About the team Amazon is investing heavily in building a world-class advertising business. This team defines and delivers a collection of advertising products that drive discovery and sales. Our solutions generate billions in revenue and drive long-term growth for Amazon’s Retail and Marketplace businesses. We deliver billions of ad impressions, millions of clicks daily, and break fresh ground to create world-class products. We are a highly motivated, collaborative, and fun-loving team with an entrepreneurial spirit - with a broad mandate to experiment and innovate. You will invent new experiences and influence customer-facing shopping experiences to help suppliers grow their retail business and the auction dynamics that leverage native advertising; this is your opportunity to work within the fastest-growing businesses across all of Amazon! Define a long-term science vision for our advertising business, driven from our customers' needs, translating that direction into specific plans for research and applied scientists, as well as engineering and product teams. This role combines science leadership, organizational ability, technical strength, product focus, and business understanding. We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA
Principal Applied Scientist, Global Talent Management & Compensation
US, WA, Seattle
Interested in using the latest, cutting edge machine learning and science to improve the Amazon employee experience? This role provides applied science leadership to the organization that develops and delivers data-driven insights, personalization, and nudges into Amazon's suite of talent management products to help managers, employees, and organizational leaders make better decisions and have better, more equitable outcomes. Key job responsibilities As the Principal Applied Scientist for GTMC SIERRA, you will be responsible for providing scientific thought leadership over multiple applied science and engineering teams. Each of these teams has rapidly evolving and complex demands to define, develop, and deliver scalable products that make work easier, more efficient, and more rewarding for Amazonians. These are some of Amazon’s most strategic technical investments in the people space and support Amazon’s efforts to be Earth’s Best Employer. In this role you will have a significant impact on 1.5 million Amazonians and the communities Amazon serves. You will also play a critical role in the organization's business planning, work closely with senior executives to develop goals and resource requirements, influence our long-term technical and business strategy, and help hire and develop engineering and science talent. You will provide science thought leadership and support to business partners, helping them use the best scientific methods and science-driven tools to solve current and upcoming challenges and deliver efficiency gains in a changing market. About the team Global Talent Management & Compensation (GTMC) SIERRA (Science, Insights, Experience, Research, Reporting & Analytics) is a horizontal, multi-disciplinary organization whose mission is to be a force multiplier for the broader GTMC organization and our key customer cohorts. We accomplish this by using our expertise in data analytics and science, economics, machine learning (ML), UX, I/O psychology, and engineering to build insights and experiences that raise the bar in understanding and shaping decision making at scale by integrating within and across talent journeys as well as through self-service tools and closed loop mechanisms outside of those journeys. Our portfolio of products spans foundational data sources, metrics, and research through to finished features and products that our end-customers interact with on a daily basis. We are open to hiring candidates to work out of one of the following locations: Seattle, WA, USA
Economist, PXT Central Science
US, VA, Arlington
The People eXperience and Technology Central Science Team (PXTCS) uses economics, behavioral science, statistics, and machine learning to proactively identify mechanisms and process improvements which simultaneously improve Amazon and the lives, wellbeing, and the value of work to Amazonians. We are an interdisciplinary team that combines the talents of science and engineering to develop and deliver solutions that measurably achieve this goal. We are looking for economists who are able to apply economic methods to address business problems. The ideal candidate will work with engineers and computer scientists to estimate models and algorithms on large scale data, design pilots and measure their impact, and transform successful prototypes into improved policies and programs at scale. We are looking for creative thinkers who can combine a strong technical economic toolbox with a desire to learn from other disciplines, and who know how to execute and deliver on big ideas as part of an interdisciplinary technical team. Ideal candidates will work in a team setting with individuals from diverse disciplines and backgrounds. They will work with teammates to develop scientific models and conduct the data analysis, modeling, and experimentation that is necessary for estimating and validating models. They will work closely with engineering teams to develop scalable data resources to support rapid insights, and take successful models and findings into production as new products and services. They will be customer-centric and will communicate scientific approaches and findings to business leaders, listening to and incorporate their feedback, and delivering successful scientific solutions. Key job responsibilities Use reduced-form causal analysis and/or structural economic modeling methods to evaluate the impact of policies on employee outcomes, and examine how external labor market and economic conditions impact Amazon's ability to hire and retain talent. A day in the life Work with teammates to apply economic methods to business problems. This might include identifying the appropriate research questions, writing code to implement a DID analysis or estimate a structural model, or writing and presenting a document with findings to business leaders. Our economists also collaborate with partner teams throughout the process, from understanding their challenges, to developing a research agenda that will address those challenges, to help them implement solutions. About the team We are a multidisciplinary team that combines the talents of science and engineering to develop innovative solutions to make Amazon Earth's Best Employer. We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA
Actuarial Analyst, Global Risk Management & Claims
US, WA, Seattle
We are expanding our Global Risk Management & Claims team and insurance program support for Amazon’s growing risk portfolio. This role will partner with our risk managers to develop pricing models, determine rate adequacy, build underwriting and claims dashboards, estimate reserves, and provide other analytical support for financially prudent decision making. As a member of the Global Risk Management team, this role will provide actuarial support for Amazon’s worldwide operation. Key job responsibilities ● Collaborate with risk management and claims team to identify insurance gaps, propose solutions, and measure impacts insurance brings to the business ● Develop pricing mechanisms for new and existing insurance programs utilizing actuarial skills and training in innovative ways ● Build actuarial forecasts and analyses for businesses under rapid growth, including trend studies, loss distribution analysis, ILF development, and industry benchmarks ● Design actual vs expected and other metrics dashboards to assist decision makings in pricing analysis ● Create processes to monitor loss cost and trends ● Propose and implement loss prevention initiatives with impact on insurance pricing in mind ● Advise underwriting decisions with analysis on driver risk profile ● Support insurance cost budgeting activities ● Collaborate with external vendors and other internal analytics teams to extract insurance insight ● Conduct other ad hoc pricing analyses and risk modeling as needed We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA | New York, NY, USA | Seattle, WA, USA
Economist, Recruiting Engine
US, WA, Seattle
The economics team within Recruiting Engine uses economics, behavioral science, statistics, and machine learning to proactively identify mechanisms and process improvements which simultaneously improve Amazon and the lives, well-being, and the value of work to Amazonians. We are an interdisciplinary team, which uses a range of approaches to develop and deliver solutions that measurably achieve this goal. We are looking for an Economist who is able to provide structure around complex business problems, hone those complex problems into specific, scientific questions, and test those questions to generate insights. The ideal candidate will work with various science, engineering, operations and analytics teams to estimate models and algorithms on large scale data, design pilots and measure their impact, and transform successful prototypes into improved policies and programs at scale. She/He/They will produce robust, objective research results and insights which can be communicated to a broad audience inside and outside of Amazon. Ideal candidates will work closely with business partners to develop science that solves the most important business challenges. She/He/They will work well in a team setting with individuals from diverse disciplines and backgrounds. She/He/They will serve as an ambassador for science and a scientific resource for business teams. Ideal candidates will own the development of scientific models and manage the data analysis, modeling, and experimentation that is necessary for estimating and validating the model. They will be customer-centric – clearly communicating scientific approaches and findings to business leaders, listening to and incorporate their feedback, and delivering successful scientific solutions. We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA | Seattle, WA, USA
View from space of a connected network around planet Earth representing the Internet of Things.
Get more from Amazon Science
Sign up for our newsletter
Subscribe
Amazon.com | Conditions of Use | Privacy | © 1996-2023 Amazon.com, Inc. or its affiliates
Follow Us